路径总和 图解题解

这道题到底在问什么

输入

root=[5,4,8,11,9,13,4,7,2,...,1], target=22

输出

true

最优解：一步一步想明白

1. 3一个等价又干净的写法：与其往下加到目标，不如往下减——每走一个节点就用 target 减掉它的值；走到叶子时，如果剩余正好是 0，说明这条路径的和恰好等于目标。任一条路命中就返回 true。下面逐节点看这趟 DFS。
2. 4DFS 起点 = 根 5，目标 22先看清这棵树：根是 5，目标和是 22。接下来从根出发做 DFS——往下走就把节点值累加进路径和，走到叶子就比对；不中就回溯换岔路，直到找到命中的那条（或全部走完）。
3. 5acc += 5 → 累加和 5深度优先往下走，踏上节点 5，累加和变成 5（距目标 22 还差 17）。它还有孩子，把它留在当前路径上(绿)，继续往下深入——先走左子树。
4. 6acc += 4 → 累加和 9深度优先往下走，踏上节点 4，累加和变成 9（距目标 22 还差 13）。它还有孩子，把它留在当前路径上(绿)，继续往下深入——先走左子树。
5. 7acc += 11 → 累加和 20深度优先往下走，踏上节点 11，累加和变成 20（距目标 22 还差 2）。它还有孩子，把它留在当前路径上(绿)，继续往下深入——先走左子树。
6. 8acc += 7 → 累加和 27沿着路径往下走，踏上叶子节点 7，把它加进累加和：现在这条根→叶路径之和是 27。没有孩子了，下一步就看这个和等不等于目标 22。
7. 9路径和 27 ≠ 22 → 这条不行到叶子了，比对：这条路径之和 27，离目标 22 还差 -5，不相等。这条根→叶路走不通，下一步要回溯：退回上一个分叉，把刚加的减掉，换另一条岔路再试。
8. 10acc -= 7 → 退回到 20节点 7 这一侧已经探完（没有满足的路径），回溯：把它从当前路径弹出、累加和减回 20，并标蓝表示「这块走过了」。回到节点 11，换它的另一条岔路继续试。
9. 11acc += 2 → 累加和 22沿着路径往下走，踏上叶子节点 2，把它加进累加和：现在这条根→叶路径之和是 22。没有孩子了，下一步就看这个和等不等于目标 22。
10. 12路径和 22 == 目标 22 → 存在到叶子了，比对：这条路径 5+4+11+2 = 22，正好等于目标 22！找到一条满足的根→叶路径，答案就是 存在(true)，整棵树标绿这条路。
11. 13acc -= 2 → 退回到 20节点 2 这条命中路径已确认，回溯：把它从当前路径弹出、累加和减回 20，并标蓝表示「这块走过了」。回到节点 11，继续演示完整 DFS、看它的另一条岔路。
12. 14acc -= 11 → 退回到 9节点 11 的两侧都探完了，其中右叶子 2 已命中，回溯：把它从当前路径弹出、累加和减回 9，并标蓝表示「这块走过了」。回到节点 4，继续演示完整 DFS。
13. 15acc += 9 → 累加和 18沿着路径往下走，踏上叶子节点 9，把它加进累加和：现在这条根→叶路径之和是 18。没有孩子了，下一步就看这个和等不等于目标 22。
14. 16路径和 18 ≠ 22 → 这条不行到叶子了，比对：这条路径之和 18，离目标 22 还差 4，不相等。这条根→叶路走不通，下一步要回溯：退回上一个分叉，把刚加的减掉，换另一条岔路再试。
15. 17acc -= 9 → 退回到 9节点 9 这一侧已经探完（没有满足的路径），回溯：把它从当前路径弹出、累加和减回 9，并标蓝表示「这块走过了」。回到节点 4，换它的另一条岔路继续试。
16. 18acc -= 4 → 退回到 5节点 4 这一侧探完了，左支里已经有命中路径，回溯：把它从当前路径弹出、累加和减回 5，并标蓝表示「这块走过了」。回到节点 5，继续演示完整 DFS、看它的右支。
17. 19acc += 8 → 累加和 13深度优先往下走，踏上节点 8，累加和变成 13（距目标 22 还差 9）。它还有孩子，把它留在当前路径上(绿)，继续往下深入——先走左子树。
18. 20acc += 13 → 累加和 26沿着路径往下走，踏上叶子节点 13，把它加进累加和：现在这条根→叶路径之和是 26。没有孩子了，下一步就看这个和等不等于目标 22。
19. 21路径和 26 ≠ 22 → 这条不行到叶子了，比对：这条路径之和 26，离目标 22 还差 -4，不相等。这条根→叶路走不通，下一步要回溯：退回上一个分叉，把刚加的减掉，换另一条岔路再试。
20. 22acc -= 13 → 退回到 13节点 13 这一侧已经探完（没有满足的路径），回溯：把它从当前路径弹出、累加和减回 13，并标蓝表示「这块走过了」。回到节点 8，换它的另一条岔路继续试。
21. 23acc += 4 → 累加和 17深度优先往下走，踏上节点 4，累加和变成 17（距目标 22 还差 5）。它还有孩子，把它留在当前路径上(绿)，继续往下深入——先走左子树。
22. 24acc += 1 → 累加和 18沿着路径往下走，踏上叶子节点 1，把它加进累加和：现在这条根→叶路径之和是 18。没有孩子了，下一步就看这个和等不等于目标 22。
23. 25路径和 18 ≠ 22 → 这条不行到叶子了，比对：这条路径之和 18，离目标 22 还差 4，不相等。这条根→叶路走不通，下一步要回溯：退回上一个分叉，把刚加的减掉，换另一条岔路再试。
24. 26acc -= 1 → 退回到 17节点 1 这一侧已经探完（没有满足的路径），回溯：把它从当前路径弹出、累加和减回 17，并标蓝表示「这块走过了」。回到节点 4，换它的另一条岔路继续试。
25. 27acc -= 4 → 退回到 13节点 4 这一侧已经探完（没有满足的路径），回溯：把它从当前路径弹出、累加和减回 13，并标蓝表示「这块走过了」。回到节点 8，换它的另一条岔路继续试。
26. 28acc -= 8 → 退回到 5节点 8 这一侧已经探完（没有满足的路径），回溯：把它从当前路径弹出、累加和减回 5，并标蓝表示「这块走过了」。回到节点 5，换它的另一条岔路继续试。
27. 29acc -= 5 → 退回到 0根节点 5 的所有分支都探完了，此前已经找到命中路径，回溯：把它从当前路径弹出、累加和减回 0，并标蓝表示「这块走过了」。整棵树 DFS 结束。
28. 30命中路径和 = 22 → true回到全局：在所有根→叶路径里，5→4→11→2 这条的和是 22，正好等于目标 22。所以答案是 存在(true)。只要找到一条命中就够了，不必把所有路径都走完。

⚠️ 容易写错的地方

完整代码（Java / Python / C++）

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;                 // 空节点：没有路径
        int rest = targetSum - root.val;                // 往下走：减掉当前节点值
        if (root.left == null && root.right == null)    // 到叶子
            return rest == 0;                           // 剩余正好为 0 才算命中
        return hasPathSum(root.left,  rest)             // 否则左右子树任一成立即可
            || hasPathSum(root.right, rest);
    }
}

class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if root is None:                       # 空节点：没有路径
            return False
        rest = targetSum - root.val            # 往下走：减掉当前节点值
        if not root.left and not root.right:   # 到叶子
            return rest == 0                   # 剩余正好为 0 才命中
        return (self.hasPathSum(root.left,  rest)
                or self.hasPathSum(root.right, rest))

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return false;              // 空节点：没有路径
        int rest = targetSum - root->val;               // 往下走：减掉当前节点值
        if (!root->left && !root->right)                // 到叶子
            return rest == 0;                           // 剩余正好为 0 才命中
        return hasPathSum(root->left,  rest)            // 否则左右任一成立即可
            || hasPathSum(root->right, rest);
    }
};

复杂度

面试官可能追问