力扣labuladong——一刷day55

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

二叉树的遍历代码是动态规划和回溯算法的祖宗。 动态规划 的关键在于明确递归函数的定义，把用子问题的结果推导出大问题的结果。 回溯算法 就简单粗暴多了，就是单纯的遍历回溯树。

一、力扣951. 翻转等价二叉树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean flipEquiv(TreeNode root1, TreeNode root2) {if(root1 == null && root2 == null){return true;}if(root1 == null || root2 == null){return false;}if(root1.val != root2.val){return false;}return (flipEquiv(root1.left,root2.left) && flipEquiv(root1.right,root2.right)) || (flipEquiv(root1.left,root2.right) && flipEquiv(root1.right,root2.left));}
}

二、力扣124. 二叉树中的最大路径和

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int res = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {fun(root);return res;}public int fun(TreeNode root){if(root == null){return 0;}int l = Math.max(0,fun(root.left));int r = Math.max(0,fun(root.right));res = Math.max(res,l+r+root.val);return Math.max(l,r) + root.val;}
}

三、力扣112. 路径总和（遍历）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {boolean flag = false;public boolean hasPathSum(TreeNode root, int targetSum) {if(root == null){return false;}fun(root,targetSum,0);return flag;}public void fun(TreeNode root, int targetSum, int path){if(root == null){return;}if(root.left == null && root.right == null){if(path + root.val == targetSum){flag = true;}return;}fun(root.left,targetSum,path+root.val);fun(root.right,targetSum,path+root.val);}
}

四、力扣112. 路径总和（分解）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if(root == null){return false;}if(root.left == root.right && root.val == targetSum){return true;}return hasPathSum(root.left,targetSum - root.val) || hasPathSum(root.right,targetSum-root.val);}
}