java算法day15

-113 路径总和 Ⅱ

437 路径总和 Ⅲ
543 二叉树的直径

113 路径总和Ⅱ

直接套用Day14总结的自顶向下的模板中的路径总和模板,直接就完了.

题目中一定要看好题,只要到叶子节点的.
但是由于我用的是回溯,所以一旦到达叶子节点不建议return,而是回溯,之前老是喜欢return.

这涉及到了回溯法的本质,所以这里可以总结,当用回溯法的时候,不要随便return.而是用回溯!

/*** 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 {
//结果集List<List<Integer>> res = new ArrayList<>();
//主函数public List<List<Integer>> pathSum(TreeNode root, int targetSum) {dfs(root,targetSum,new ArrayList<>());return res;}
//递归void dfs(TreeNode root,int sum,List<Integer> path){//递归出口if(root==null){return ;}//前序遍历,上来先处理path.add(root.val);sum-=root.val;//如果是叶子节点,并且满足条件,sum=0,就收集结果if(root.left==null && root.right==null && sum == 0){res.add(new ArrayList<>(path));}else{//否则就不是叶子节点,继续递归左右子树dfs(root.left,sum,path);dfs(root.right,sum,path);}//回溯是放在归这个位置,一定要有判断哪部分代码是归的逻辑.path.remove(path.size()-1);}
}

437 路径总和Ⅲ

仍然是套用自顶向下的模板中的路径和模板.
由于只是统计个数,就没必要用回溯了,回溯一般还是用在要输出路径的题.

但本题有个特点:
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的.

这个时候也许你想到了非自顶向下做法,我只能说不好做,因为不好控制自顶向下,在这里写判断语句太难了.

解法还是自顶向下的解法,如何自顶向下?递归每个节点搞自顶向下统计不就行了吗?这种方法也许效率不高,我看了最优解要用到前缀和,我还不会,所以这是目前我会的解法.

还有个要注意的,我在有个特殊样例过不去,改成long就过得去了.

/*** 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 count = 0;//由于有双重递归,所以另外一个递归还是再开一个函数public int pathSum(TreeNode root, int targetSum) {dfsPathSum(root, targetSum);return count;}//用于递归每个节点做自顶向下private void dfsPathSum(TreeNode root, int targetSum) {//递归出口if (root == null) {return;}//每个节点做自顶向下统计dfs(root, (long)targetSum);//递归左右子树dfsPathSum(root.left, targetSum);dfsPathSum(root.right, targetSum);}//用于统计节点做自顶向下符合的结果private void dfs(TreeNode root, long sum) {//递归出口if (root == null) {return;}//当前节点处理sum -= (long)root.val;//判断是否收集结果if (sum == 0) {count++;}//递归左右子树dfs(root.left, sum);dfs(root.right, sum);}
}

543 二叉树的直径

直接套非自顶向下模板,而且他不要统计节点和,只要边的数量,那么按我们模板就是对节点进行了处理,所以可以推理,边和点的关系是n-1
n个点,n-1条边.

这里递归的理解,变成了计算左右子树中点的个数了,res变成了左子树点的个数+右子树点的个数+本身节点.

所以由于是自底向上,那么要返回的也是左右子树中哪条分支节点最多.

/*** 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 {
//结果private int res = 0;//主函数public int diameterOfBinaryTree(TreeNode root) {maxPath(root);return res-1;}
//递归private int maxPath(TreeNode root){//递归出口if(root==null){return 0;}//计算左右子树的节点个数int left = maxPath(root.left);int right = maxPath(root.right);//这里已经是归的逻辑了//更新结果res = Math.max(res,left+right+1);//向上返回左右子树中最大的节点个数那条分支,并且加上本层的return Math.max(left,right)+1;}
}

java算法day15