1.相比于无返回值的dfs函数，一般推荐创建带返回值的dfs函数，因为更灵活，但是难度也比较大；

1.二叉树的最大深度

image.png

无返回值的dfs

  1. public int maxDepth(TreeNode root) {
  2.         dfs(root,1);
  3.         return maxD;
  4.     }
  5.     public void dfs(TreeNode root,int depth){
  6.         if(root==null){
  7.             maxD=Math.max(maxD,depth-1);
  8.             return;
  9.         }
  10.         dfs(root.left,depth++);
  11.         dfs(root.right,depth++);
  12.     }

注意点：

  1. root==null时depth已经加1，实际深度是depth-1
  2. 函数参数中不能使用自增或自减操作，切记

有返回值的dfs

  1. class Solution {
  2.     public int maxDepth(TreeNode root) {
  3.         return dfs(root);
  4.     }
  5.     public int dfs(TreeNode root){
  6.         if(root==null){
  7.             return 0;
  8.         }
  9.         return Math.max(dfs(root.left),dfs(root.right))+1;
  10.     }
  11. }

每个节点的深度等于左子树深度和右子树深度的最大值再加1
当节点为null时返回0，意味着叶子节点的深度为1，然后慢慢倒推
有返回值的dfs代码看起来更简洁

2.二叉树的最小深度

image.png

无返回值的dfs

  1. class Solution {
  2.     public int minD=100000;
  3.     public int minDepth(TreeNode root) {
  4.         if(root==null){
  5.             return 0;
  6.         }
  7.         dfs(root,1);
  8.         return minD;
  9.     }
  11.     public void dfs(TreeNode root,int depth){
  12.         if(root==null){
  13.             return ;
  14.         }
  15.         if(root.left==null && root.right==null){
  16.             minD=Math.min(minD,depth);
  17.             return;
  18.         }
  19.         dfs(root.left,depth+1);
  20.         dfs(root.right,depth+1);
  21.     }
  22. }

因为从根节点到叶子节点才算一个合格的路径，
所以要在递归的过程中要判断当前节点是否是叶子节点，如果是就可以更新minD
代码中还多了两处判断root是否为空的代码，整体结构比较零散

带返回值的dfs

  1. class Solution {
  2.     public int minDepth(TreeNode root) {
  3.         if(root==null){
  4.             return 0;
  5.         }
  6.         return dfs(root);
  7.     }
  9.     public int dfs(TreeNode root){
  10.         if(root==null){
  11.             return 1000000 ;
  12.         }
  13.         if(root.left==null && root.right==null){
  14.             return 1;
  15.         }
  16.         return Math.min(dfs(root.left),dfs(root.right))+1;
  17.     }
  18. }

同样多了两处判断root是否为空，整体结构比较零散
dfs中的root==null的return 1000000的目的是不考虑当前分支作为父节点的深度参考

我之前的思想：

  1. class Solution {
  2.     public int minDepth(TreeNode root) {
  3.         return dfs(root);
  4.     }
  5.     public int dfs(TreeNode root){
  6.         if(root==null){
  7.             return 0;
  8.         }
  9.         int leftHeight=dfs(root.left);
  10.         int rightHeight=dfs(root.right);
  11.         if(root.left==null){
  12.             return rightHeight+1;
  13.         }else if(root.right==null){
  14.             return leftHeight+1;
  15.         }else{
  16.             return Math.min(leftHeight,rightHeight)+1; 
  17.         }
  18.     }
  19. }

上面的思想不是借助判断叶子节点；
而是左子树为空时就考虑右子树，同理，右子树为空时就考虑左子树；

3.路径总和

image.png
image.png

有返回值的dfs（这已经是复杂成了回溯了）

  1. class Solution {
  2.     ArrayList<Integer> list=new ArrayList();
  3.     public boolean hasPathSum(TreeNode root, int targetSum) {
  4.         if(root==null){
  5.             return false;
  6.         }
  7.         list.add(root.val);
  8.         return dfs(root,targetSum);
  9.     }
  10.     public boolean dfs(TreeNode root,int targetSum){
  11.         // if(root==null){
  12.         //     return false;
  13.         // }
  14.         if(root.left==null && root.right==null){
  15.             int sum=0;
  16.             for(int i=0;i<list.size();i++){
  17.                 sum=sum+list.get(i);
  18.             }
  20.             if(sum==targetSum){
  21.                 return true;
  22.             }else{
  23.                 return false;
  24.             }
  25.         }
  26.         boolean b1=false;
  27.         boolean b2=false;
  28.         if(root.left!=null){
  29.             list.add(root.left.val);
  30.             b1=dfs(root.left,targetSum);
  31.             list.remove(list.size()-1);
  32.         }
  33.         if(root.right!=null){
  34.             list.add(root.right.val);
  35.             b2=dfs(root.right,targetSum);
  36.             list.remove(list.size()-1);
  37.         }
  38.         return b1 || b2;
  40.     }
  41. }

思想：
使用回溯：
当前节点往下就两个选择，要么左子树，要么右子树；
如果左子树存在就将左节点放进列表中，递归后再取消；
如果右子树存在就将右节点放进列表中，递归后再取消；
注意每一次存和删的都是左子节点和右子节点，那当前节点呢？
这里需要知道二叉树中除了根节点，每个节点都是其他节点的左节点或者右节点；
所以这里只需要一开始就将根节点放进列表中就行，根节点全程只管进，不管出，符合题意；
dfs中不需要判断if(root==null)，因为root=null进不了dfs

有返回值的dfs

  1. class Solution {
  2.     public boolean hasPathSum(TreeNode root, int targetSum) {
  3.         return dfs(root,targetSum);
  4.     }
  5.     public boolean dfs(TreeNode root,int targetSum){
  6.         if(root==null){
  7.             return false;
  8.         }
  9.         if(root.left==null && root.right ==null){
  10.             // if(targetSum==0){
  11.             //     return true;
  12.             // }else{
  13.             //     return false;
  14.             // }
  15.             return (targetSum==root.val);
  16.         }
  17.         return dfs(root.left,targetSum-root.val) || dfs(root.right,targetSum-root.val);
  19.     }
  20. }

这里用targetSum自动维护每一个节点的状态
注意当到达叶子节点的时候是判断targetSum与root.val的大小，而不是跟0的大小
另外注释的代码太垃圾了，一行的代码写成四行，面试官直接辞退

比较

什么时候非得用回溯？
回溯的话用于每条路径的中间的每个选择都需要获取，比如全排列问题，需要维护一个集合；
dfs的话只关注最终的值，只要最终值合适即可，不关注中间的选择，只需要维护一个变化的参数；

4.路径总和II

image.png
image.png

原来这才是我的回溯对应的题目

  1. class Solution {
  2.     List<List<Integer>> res=new ArrayList<List<Integer>>();
  3.     ArrayList<Integer> list=new ArrayList();
  4.     public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
  5.         if(root==null){
  6.             return new ArrayList<List<Integer>>();//这里不能返回null
  7.         }
  8.         list.add(root.val);
  9.         dfs(root,targetSum);
  10.         return res;
  11.     }
  12.      public boolean dfs(TreeNode root,int targetSum){
  13.         if(root.left==null && root.right==null){
  14.             int sum=0;
  15.             for(int i=0;i<list.size();i++){
  16.                 sum=sum+list.get(i);
  17.             }
  19.             if(sum==targetSum){
  20.                 res.add(new ArrayList<Integer>(list));//必须用new，因为list在回溯中仅一份
  21.                 return true;
  22.             }else{
  23.                 return false;
  24.             }
  25.         }
  26.         boolean b1=false;
  27.         boolean b2=false;
  28.         if(root.left!=null){
  29.             list.add(root.left.val);
  30.             b1=dfs(root.left,targetSum);
  31.             list.remove(list.size()-1);
  32.         }
  33.         if(root.right!=null){
  34.             list.add(root.right.val);
  35.             b2=dfs(root.right,targetSum);
  36.             list.remove(list.size()-1);
  37.         }
  38.         return b1 || b2;
  40.     }
  41. }

官方题解：

  1. class Solution {
  2.     List<List<Integer>> ret = new LinkedList<List<Integer>>();
  3.     Deque<Integer> path = new LinkedList<Integer>();
  5.     public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
  6.         dfs(root, targetSum);
  7.         return ret;
  8.     }
  10.     public void dfs(TreeNode root, int targetSum) {
  11.         if (root == null) {
  12.             return;
  13.         }
  14.         path.offerLast(root.val);
  15.         targetSum -= root.val;
  16.         if (root.left == null && root.right == null && targetSum == 0) {
  17.             ret.add(new LinkedList<Integer>(path));
  18.         }
  19.         dfs(root.left, targetSum);
  20.         dfs(root.right, targetSum);
  21.         path.pollLast();
  22.     }
  23. }

使用当前节点进行回溯，而不是用左子节点和右子节点
这个思想确实更好，代码更简洁
我尝试根据这个思想来写写

  1. public boolean dfs(TreeNode root,int targetSum){
  2.         if(root==null){
  3.             return false;
  4.         }
  5.         if(root.left==null && root.right==null){
  6.             int sum=0;
  7.             for(int i=0;i<list.size();i++){
  8.                 sum=sum+list.get(i);
  9.             }
  10.             if(sum==targetSum){
  11.                 res.add(new ArrayList<Integer>(list));
  12.                 return true;
  13.             }else{
  14.                 return false;
  15.             }
  16.         }
  17.         list.add(root.val);
  18.         boolean b1=dfs(root.left,targetSum);
  19.         boolean b2=dfs(root.right,targetSum);
  20.         list.remove(list.size()-1);
  21.         return b1 || b2; 
  22.     }

上面代码有问题，输出的结果是空的
原因在于if中直接return会导致只有add没有remove
回溯有了add必然要有remove，而且要保证对应的两个都能执行，否则就回溯失败了

  1. public void dfs(TreeNode root,int targetSum){
  2.         if(root==null){
  3.             return ;
  4.         }
  5.         list.add(root.val);
  6.         //if判断中不能返回，因为返回的话，remove没法执行，这样只有add没有remove就不是回溯了
  7.         if(root.left==null && root.right==null){
  8.             int sum=0;
  9.             for(int i=0;i<list.size();i++){
  10.                 sum=sum+list.get(i);
  11.             }
  12.             if(sum==targetSum){
  13.                 res.add(new ArrayList<Integer>(list));
  14.             }
  15.         }
  16.         // list.add(root.val);
  17.         dfs(root.left,targetSum);
  18.         dfs(root.right,targetSum);
  19.         list.remove(list.size()-1);
  20.     }
  1. public void dfs(TreeNode root,int targetSum){
  2.         if(root==null){
  3.             return ;
  4.         }
  5.         if(root.left==null && root.right==null){
  6.             list.add(root.val);//多加判断1
  7.             int sum=0;
  8.             for(int i=0;i<list.size();i++){
  9.                 sum=sum+list.get(i);
  10.             }
  11.             if(sum==targetSum){
  12.                 res.add(new ArrayList<Integer>(list));
  13.             }
  14.             list.remove(list.size()-1);//多加判断2
  15.         }
  16.         list.add(root.val);//放在这里看着结构好看，上面的if判断就得多加两行
  17.         dfs(root.left,targetSum);
  18.         dfs(root.right,targetSum);
  19.         list.remove(list.size()-1);
  20.     }
  1.   public boolean dfs(TreeNode root,int targetSum){
  2.         if(root==null){
  3.             return false;
  4.         }
  5.         if(root.left==null && root.right==null){
  6.             list.add(root.val);//添加当前节点，此时为叶子节点
  7.             int sum=0;
  8.             for(int i=0;i<list.size();i++){
  9.                 sum=sum+list.get(i);
  10.             }
  11.             if(sum==targetSum){
  12.                 res.add(new ArrayList<Integer>(list));
  13.                 list.remove(list.size()-1);//删除当前节点，此时为叶子节点
  14.                 return true;
  15.             }else{
  16.                 list.remove(list.size()-1);//删除当前节点，此时为叶子节点
  17.                 return false;
  18.             }
  19.         }
  20.         list.add(root.val);//添加当前节点，此时不是叶子节点
  21.         boolean b1=dfs(root.left,targetSum);
  22.         boolean b2=dfs(root.right,targetSum);
  23.         list.remove(list.size()-1);
  24.         return  b1||b2;//带返回值的情况也可以！！！
  25.     }

回溯方法的参数int targetSum这里是不变的
如果将其设定为可变的
那么就可以看在叶子结点处是否为0，而不需要遍历List集合来求和
这个可变的参数在很多dfs和回溯中用到（先给一个设定值，然后每次减去当前值）
比如括号生成等

5.路径总和III

image.png

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public int pathSum(TreeNode root, int targetSum) {
  18.         //key为前缀和，value为次数
  19.         Map<Integer,Integer> map=new HashMap();
  20.         //map.put(0,1)解释：比如根节点的val为n，targetSum也为n,此时根节点本身就是路径，但是按照下面的代码会将其设置为0，所以要加1;
  21.         //不仅如此，当curSum第一次累加到target，本应该将key为0的value设置为1，但是按照res=res+map..的话，此时依旧为0
  22.         map.put(0,1);
  23.         return dfs(root,map,targetSum,0);
  24.     }
  25.     public int dfs(TreeNode root,Map<Integer,Integer> map,int target,int curSum){
  26.         if(root==null){
  27.             return 0;
  28.         }
  29.         int res=0;
  30.         curSum=curSum+root.val;
  31.         res=res+map.getOrDefault(curSum-target,0);
  32.         map.put(curSum,map.getOrDefault(curSum,0)+1);
  33.         // if(map.containsKey(curSum-target)){
  34.         //     res=res+map.get(curSum-target);
  35.         // }
  36.         res=res+dfs(root.left,map,target,curSum);
  37.         res=res+dfs(root.right,map,target,curSum);
  38.         map.put(curSum,map.get(curSum)-1);
  39.         return res;
  40.     }
  41. }