二叉树中和为某一值的路径

---

题目：

题解：

1、回溯法

• 解题思路：

  • 先序遍历： 按照 “根、左、右” 的顺序，遍历树的所有节点。
  • 路径记录： 在先序遍历中，记录从根节点到当前节点的路径。当路径为 ① 根节点到叶节点形成的路径 且 ② 各节点值的和等于目标值 sum 时，将此路径加入结果列表。

• 复杂度分析：

  • 时间复杂度 O(N) ： N 为二叉树的节点数，先序遍历需要遍历所有节点。
  • 空间复杂度 O(N) ： 最差情况下，即树退化为链表时，path 存储所有树节点，使用 O(N) 额外空间。

• 值得注意的是，记录路径时若直接执行 res.add(path) ，则是将 path 对象加入了 res ；后续 path 改变时， res 中的 path 对象也会随之改变。

  正确做法：res.add(new LinkedList(path)) ，相当于复制了一个 path 并加入到 res 。

  • 深拷贝：开辟一个独立地址，地址中存放的内容为list链表，后续list的变化不会影响到res。
  • 浅拷贝：将res尾部指向了list地址，后续list内容的变化会导致res的变化，所以res输出为空。

• 代码：

  class Solution {
      // 初始化返回的list
      List<List<Integer>> res = new LinkedList<>();
      // 记录返回路径
      LinkedList<Integer> path = new LinkedList<>();
      public List<List<Integer>> pathSum(TreeNode root, int target) {
          dfs(root,target);
          return res;
      }
  
      // 先序遍历 + 路径记录
      private void dfs(TreeNode root, int target) {
          if (root == null) {
              return;
          }
          // 将root的值存入路径集合中
          path.add(root.val);
          // target减去此时指针的值
          target -= root.val;
          // 判断，如果target = 0，并且还是叶子节点，则说明这条路径是走完了，且是符合条件的路径，则将path赋给res
          if (target == 0 && root.left == null && root.right == null) {
              res.add(new LinkedList<>(path));
          }
          dfs(root.left,target);
          dfs(root.right,target);
          path.removeLast();
  
      }
  }