算法训练营day17 | {513.找树左下角的值, 112.路径总和, 106.从中序与后序遍历序列构造二叉树}

第六章二叉树part04，继续练习递归三步曲，注意局部变量什么时候需要回溯、什么时候不需要。

513. 找树左下角的值

• 题目链接：513. 找树左下角的值
• 文档讲解：代码随想录–513. 找树左下角的值
• 视频讲解：怎么找二叉树的左下角？ 递归中又带回溯了，怎么办？| LeetCode：513.找二叉树左下角的值
• 状态：本题适用于前序遍历，但似乎涉及到回溯。

1.1 解题分析

• 要求的最底层的第一个节点值，并不一定是左孩子，我题意就理解错了。久命。

• 等价于求深度最大的第一个叶节点，本题递归使用前序、中序、后序遍历都可以，因为中不做任何处理，只要保证左右 左先遍历到即可。

• 分析递归三步曲

  1. 参数和返回值是什么？ 要传入一个根节点，一个depth记录深度。返回void。全局变量result记录结果值。
  2. 确定递归的终止条件。 当遍历到叶节点时终止递归，同时在这里判断最大深度是否比之前更高，如果是，更新结果值。
  3. 确定单层递归的逻辑。 前序遍历，中左右，递归左子树，递归右子树，深度+1（一个递归对应一个回溯）

• 层序遍历做这道题很简单。会了跳过。

1.2 解题小结

• 前序遍历–递归+回溯

  ▶

  513. 找树左下角的值

  class Solution {
      int maxDepth = Integer.MIN_VALUE;
      int result;
      
      public int findBottomLeftValue(TreeNode root) {
          preOrder(root, 1);
          return result;
      }
  
      public void preOrder(TreeNode node, int depth) {
          if (node.left == null && node.right == null) {
              if (maxDepth < depth) {
                  result = node.val;
                  maxDepth = depth;
              }
              return;
          }
          if(node.left != null) {
              depth++;
              preOrder(node.left, depth);
              depth--;
          }
          if(node.right != null) {
              depth++;
              preOrder(node.right, depth);
              depth--;
          }
      }
  }

• 前序遍历–递归+回溯（回溯隐藏在传参中）

  ▶

  513. 找树左下角的值

  class Solution {
      int maxDepth = Integer.MIN_VALUE;
      int result;
  
      public int findBottomLeftValue(TreeNode root) {
          preOrder(root, 1);
          return result;
      }
  
      public void preOrder(TreeNode node, int depth) {
          if (node.left == null && node.right == null) {
              if (maxDepth < depth) {
                  result = node.val;
                  maxDepth = depth;
              }
              return;
          }
          if(node.left != null) preOrder(node.left, depth + 1);
          if(node.right != null) preOrder(node.right, depth+1);
      }
  }

112. 路径总和

• 题目链接：112. 路径总和
• 文档讲解：代码随想录–112. 路径总和
• 视频讲解：拿不准的遍历顺序，搞不清的回溯过程，我太难了！ | LeetCode：112. 路径总和
• 状态：路径总和本质上是一个自顶向下的问题。适合先处理当前节点，再处理子树，是前序遍历的语义。

2.1 解题分析

• 本题找到一个可行的路径就可以终止，不需要遍历整个树。
• 计数器参数传入TargetSum，做减法不做加法回溯起来更方便。
• 分析递归三步曲
  1. 参数和返回值是什么？ 要传入一个根节点，一个int类型的计数器；返回值为boolean类型。
  2. 确定递归的终止条件。 如果遍历到叶子节点并且刚好和为目标值，则返回true，如果遍历到叶子节点但和不等于目标值，返回false。
  3. 确定单层递归的逻辑。 中左右。注意因为递归函数有返回值，所以当某个父节点调用子节点递归，结果返回true时，找到可行解，继续向上返回true。

2.2 递归函数的返回值

• 递归函数什么时候需要返回值？什么时候不需要返回值？
  1. 第一类：父节点要根据子节点的结果来做判断或计算。
     • 返回boolean/int/Treenode
     • 子递归结果会被用来判断/计算/组合
     • 模板

       boolean dfs(node) {
           boolean left = dfs(node.left);
           boolean right = dfs(node.right);
           return 某个基于 left / right 的结果;
       }

  • 总结目前写过的题，属于这一类的有：

  • 题目	返回值
    112路径总和	boolean
    110平衡二叉树	int（高度）
    101对称二叉树	boolean
    404左叶子之和	int

  2. 第二类：递归只是为了“遍历+修改外部状态”
     • 返回void
     • 真正的结果存在：
       • 全局变量
       • 传入的List/StringBuilder中
     • 模板

       void dfs(node) {
              做一些事;
              dfs(node.left);
              dfs(node.right);
          }

     • 常见的场景包括：收集路径、收集所有结果、存储节点。

2.3 关于回溯

• 回溯 = 改了某个共享变量，用完必须改回去
• 本题不需要对count回溯，因为
  • count是一个基本类型int；
  • Java是值传递
  • 每一层递归都会得到自己的count副本

因此我改动的是当前栈帧里的count，不是父递归里的count，不需要回溯，如果是List<>数组，比如路径收集问题，就需要回溯。

• 因为数组是引用类型
• 所有递归公用
• 不回溯就会污染其他分支

所以第一题513. 找树左下角的值其实也是值传递，不需要回溯，为了学习回溯的思想把这个过程展示出来了。

2.4 解题小结

• 前序遍历–递归

  ▶

  112. 路径总和

  class Solution {
      public boolean hasPathSum(TreeNode root, int targetSum) {
          if (root == null) return false;
          targetSum -= root.val;
          if (root.left == null && root.right == null) return targetSum == 0;
          if (root.left != null) {
              if(hasPathSum(root.left, targetSum)) return true;
          }
          if (root.right != null) {
              if (hasPathSum(root.right, targetSum)) return true;
          }
          return false;
      }
  }

• 前/中/后序遍历–视频中的解法（关键区别是count先减去当前节点的值再进入遍历）

  ▶

  112. 路径总和

  class Solution {
      public boolean hasPathSum(TreeNode root, int targetSum) {
          if (root == null) return false;
          return traversal(root, targetSum - root.val);
      }
  
      public boolean traversal(TreeNode node, int count) {
          if(node.left == null && node.right == null) return count == 0;
          if(node.left != null && traversal(node.left, count - node.left.val)) return true;
          if(node.right != null && traversal(node.right, count - node.right.val)) return true;
          return false;
      }
  }

113. 路径总和II

本题明确要求收集所有符合条件的路径，递归只是为了遍历，不需要返回值。参数是引用类型，需要回溯。

• 分析递归三步曲：

  1. 参数和返回值是什么？ 要传入一个根节点，一个int计数器，一个记录路径的数组，一个结果集数组。
  2. 确定递归的终止条件。 当遍历到叶子节点且count刚好为0时，找到一个可行解，计入结果集数组。
  3. 确定单层递归的逻辑。 任意遍历，中左右，如果左子树不为空，减去左子树节点的节点值，把节点加入path数组，接着递归调用左子树；右子树一样处理。注意对引用类型进行回溯。

• 第一遍解题，前序+回溯的思路是对的，但有3个小错误，也有涉及JAVA API用法

  1. 路径没有加根节点。 我在调用前targetSum - root.val，但是没有把root.val加入path路径，导致所有路径都缺少根节点；
  2. 左右子树相互污染了count状态。 count作为同一个局部变量，在left分支扣了一次，right分支用的是已经被扣过的count，应该不改当前count；
  3. result.add(path)直接加入引用，没有拷贝。 这代表：
     • path是一个对象
     • 我加入的是同一个引用
     • 后续path.pollLast()会修改它
     • 最终result里所有路径都指向它，并且都为空
     • 正确做法：必须深拷贝

       result.add(new ArrayList<>(path));

• 总结：113 = 前序遍历 + 回溯 + 深拷贝

  • 进入节点：path.add
  • 离开节点：path.remove
  • 加入结果：new ArrayList<>(path)

▶

113. 路径总和II

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ans = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        if(root == null) return ans;
        path.offerLast(root.val);
        preOrder(root, targetSum - root.val, path, ans);
        path.pollLast();
        return ans;
    }

    public void preOrder(TreeNode node, int count, LinkedList<Integer> path, List<List<Integer>> result) {
        if(node.left == null && node.right == null && count == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        if(node.left != null) {
            path.offerLast(node.left.val);
            preOrder(node.left, count - node.left.val, path, result);
            path.pollLast();
        }
        if(node.right != null) {
            path.offerLast(node.right.val);
            preOrder(node.right, count - node.right.val, path, result);
            path.pollLast();
        }
    }
}

2.5.1 JAVA API 细节

• 第一遍我把path定义为LinkedList数组类型，因为需要回溯，但这个类型效率不是最高的（链表不是连续内存，每个节点是对象，前后都有指针内存占用大），在面试中更推荐使用ArrayList + 回溯，或者ArrayDeque循环数组。

  • ArrayList + 回溯

    原来可以通过path.size() - 1确定弹出最后一个元素，学到了。

    List<Integer> path = new ArrayList<>();
    
    path.add(node.val);
    dfs(...);
    path.remove(path.size() - 1);

  • ArrayDeque + 回溯

    Deque<Integer> path = new ArrayDeque<>();
    
    path.addLast(node.val);
    dfs(...);
    path.removeLast();

▶

113. 路径总和II

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if(root == null) return ans;
        path.add(root.val);
        preOrder(root, targetSum - root.val, path, ans);
        path.remove(path.size() - 1);
        return ans;
    }

    public void preOrder(TreeNode node, int count, List<Integer> path, List<List<Integer>> result) {
        if(node.left == null && node.right == null && count == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        if(node.left != null) {
            path.add(node.left.val);
            preOrder(node.left, count - node.left.val, path, result);
            path.remove(path.size() - 1);
        }
        if(node.right != null) {
            path.add(node.right.val);
            preOrder(node.right, count - node.right.val, path, result);
            path.remove(path.size()-1);
        }
    }
}

2.5.2 关于path深拷贝

• 这句代码的真实含义是：把path这个对象的地址，放进result里。回溯会修改这个引用指向的对象，所以必须用深拷贝保存一份当时的快照。

  List<Integer> path = new ArrayList<>();
  result.add(path);

• 这行代码做了什么？

  new ArrayList<>(path);

  它会：
  1. 创建一个新的ArrayList对象；
  2. 把path里当前的元素逐个复制进去；
  3. 返回一个和path内容相同，但完全独立的对象

106. 从中序与后序遍历序列构造二叉树

• 题目链接：106. 从中序与后序遍历序列构造二叉树
• 文档讲解：代码随想录–106. 从中序与后序遍历序列构造二叉树
• 视频讲解：坑很多！来看看你掉过几次坑 | LeetCode：106.从中序与后序遍历序列构造二叉树
• 状态：考研过的都会思路，利用后序遍历找根节点，去分割中序遍历，找到左右子树，递归左右子树找根节点。

3.1 解题分析

• 题目给了前提条件，inorder和postorder都由不同的值组成。
• 本题对我来说，难点在于确定递归的终止条件，只看后序数组（视频讲解），当后序数组为0时，返回空节点；或者当后序数组中有一个元素时，构造好节点之后return。
• 做题步骤（画个图分析就清楚了）
  1. 后序数组为0，空节点；
  2. 后序数组最后一个元素为节点元素
  3. 寻找中序数组位置作为切割点
  4. 切中序数组
  5. 切后序数组
  6. 递归处理左区间右区间

3.2 解题小结

• 切后序数组的时候，注意是依据中序数组的长度来切分。（举例画图看着写就简单）

  ▶

  106. 从中序与后序遍历序列构造二叉树

  public class Solution {
      public TreeNode buildTree(int[] inorder, int[] postorder) {
          if (postorder.length == 0) return null;
          TreeNode root = new TreeNode(postorder[postorder.length - 1]);
          if (postorder.length == 1) return root;
          int index = 0;
          for (int i = 0; i < inorder.length; i++) {
              if (inorder[i] == postorder[postorder.length - 1]) {
                  index = i;
                  break;
              }
          }
          int[] inLeft = new int[index];
          System.arraycopy(inorder, 0, inLeft, 0, index);
          int[] inRight = new int[inorder.length - index - 1];
          System.arraycopy(inorder, index + 1, inRight, 0, inRight.length);
          int[] postLeft = new int[index];
          System.arraycopy(postorder, 0, postLeft, 0, index);
          int[] postRight = new int[inRight.length];
          System.arraycopy(postorder, inLeft.length, postRight, 0, inRight.length);
  
          root.left = buildTree(inLeft, postLeft);
          root.right = buildTree(inRight, postRight);
          return root;
      }
  }

• System.arraycopy是native方法，本身并不慢，但是我在递归中反复调用它，对于每一层递归：

  • 都在新建4个数组
  • 都在复制O(n)的数据
  • 整个树递归下来，总时间复杂度退化为O(n^2)，出现在树极端不平衡的时候；空间复杂度也很高(大量临时数组)。

• 应该换一种思路，数组本身不用切，用下标区间来表示子数组;

• 再加上一个关键优化：用HashMap记录inorder中每个值的位置，避免每次O(n)去找根节点。

▶

106. 从中序与后序遍历序列构造二叉树

class Solution {
    private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        indexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    public TreeNode build(int[] inorder, int inLeft, int inRight, int[] postorder, int postLeft, int postRight) {
        if (postLeft > postRight) return null;
        int rootVal = postorder[postRight];
        TreeNode root = new TreeNode(rootVal);
        int index = indexMap.get(rootVal);
        int leftSize = index - inLeft;  // 错误点：只有个数可以传递，下标并不对齐

        root.left = build(inorder, inLeft, index - 1, postorder, postLeft, postLeft + leftSize - 1);
        root.right = build(inorder, index + 1, inRight, postorder, postLeft + leftSize, postRight - 1);
        return root;
    }
}

105. 从前序与中序遍历序列构造二叉树

• 第一遍写还是没搞清楚递归的语义，在递归函数里，我每一层都固定用preOrder[0]当根，但实际上当前子树的根应该是preOrder[preLeft]，而不是整个树的第一个元素。前面优化106也是一样。关键是递归函数中，永远只看当前递归到的那一段子区间，不要把第一层模拟进去。

▶

105. 从前序与中序遍历序列构造二叉树

class Solution {
    private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        indexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    
    public TreeNode build(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {
        if (preLeft > preRight) return null;
        int rootVal = preorder[preLeft];
        TreeNode root = new TreeNode(rootVal);
        int index = indexMap.get(rootVal);
        int leftSize = index - inLeft;
        
        root.left = build(preorder, preLeft + 1, preLeft + leftSize, inorder, inLeft, index - 1);
        root.right = build(preorder, preLeft + leftSize + 1, preRight, inorder, index + 1, inRight);
        return root;
    }
}

4. 今日收获

• 关于JAVA API的深拷贝，对于保存快照的递归题，必须new ArrayList<>()新建一个对象；
• 关于递归函数什么时候有返回值？什么时候没有？今天算是系统地总结回顾了一下，感觉有返回值的题目更难一些。
• 关于什么时候参数需要回溯？什么时候不需要？同样做了系统的总结。
• 学习时长：6小时