网站不支持下载的视频怎么下载,网上怎么查公司信息,珠宝网站建设的主要方式,天津的网站建设公司哪家好提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣951. 翻转等价二叉树二、力扣124. 二叉树中的最大路径和三、力扣112. 路径总和#xff08;遍历#xff09;四、力扣112. 路径总和#xff08;分解文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣951. 翻转等价二叉树二、力扣124. 二叉树中的最大路径和三、力扣112. 路径总和遍历四、力扣112. 路径总和分解 前言 二叉树的遍历代码是动态规划和回溯算法的祖宗。 动态规划 的关键在于明确递归函数的定义把用子问题的结果推导出大问题的结果。 回溯算法 就简单粗暴多了就是单纯的遍历回溯树。
一、力扣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,lrroot.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,pathroot.val);fun(root.right,targetSum,pathroot.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);}
}
