面试题34_ 二叉树中和为某一值的路径.md

面试题 34 ：二叉树中和为某一值的路径

---

leetcode-cn 题目地址

📗difficulty： Medium

🎯Tags：

• 递归
• 深度优先搜索

---

1. 题目描述📃

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

样例 1 ：给定如下二叉树，以及目标和 sum = 22

			  5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

返回：

[
   [5,4,11,2],
   [5,8,4,5]
]

注意：

• 节点总数 <= 10000

注意：

• 本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/

---

2. 解题思路💡

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

正确做法： lastRes.add(new LinkedList<>(pathRes)) 相当于复制了一个 pathRes 并加入到 lastRes。

代码实现

private List<List<Integer>> lastRes = new LinkedList<>();
private LinkedList<Integer> pathRes = new LinkedList<>();

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    dfs(root, sum);
    return lastRes;
}

public void dfs(TreeNode root, int target) {
    if (root != null) {
        pathRes.add(root.val);
        target = target - root.val;
        if (target == 0 && root.left == null && root.right == null) {
            lastRes.add(new LinkedList<>(pathRes)); // copy 一份，而不是选择 clear() 方法
            // 思考为什么不能 return ？
            //                return;
        }
        dfs(root.left, target);
        dfs(root.right, target);
        // 回溯
        pathRes.removeLast();
    }
}

复杂度分析

• 时间复杂度：O(n) 。每个节点都要访问一次。
• 空间复杂度：O(n) 。最差情况下，即树退化为单链表的情况下，需要存储全部的节点。

---

3. 总结🎯

相似题目

112. 路径总和

257. 二叉树的所有路径