题目描述
思路解析动画文字版
一个等价又干净的写法：与其往下加到目标，不如往下减——每走一个节点就用 target 减掉它的值；走到叶子时，如果剩余正好是 0，说明这条路径的和恰好等于目标。任一条路命中就返回 true。下面逐节点看这趟 DFS。
准备 · 整棵树：先看清这棵树：根是 5，目标和是 22。接下来从根出发做 DFS——往下走就把节点值累加进路径和，走到叶子就比对；不中就回溯换岔路，直到找到命中的那条（或全部走完）。
走到节点 5：深度优先往下走，踏上节点 5，累加和变成 5（距目标 22 还差 17）。它还有孩子，把它留在当前路径上(绿)，继续往下深入——先走左子树。
走到节点 4：深度优先往下走，踏上节点 4，累加和变成 9（距目标 22 还差 13）。它还有孩子，把它留在当前路径上(绿)，继续往下深入——先走左子树。
走到节点 11：深度优先往下走，踏上节点 11，累加和变成 20（距目标 22 还差 2）。它还有孩子，把它留在当前路径上(绿)，继续往下深入——先走左子树。
走到节点 7 · 叶子：沿着路径往下走，踏上叶子节点 7，把它加进累加和：现在这条根→叶路径之和是 27。没有孩子了，下一步就看这个和等不等于目标 22。
不中：27 ≠ 22：到叶子了，比对：这条路径之和 27，离目标 22 还差 -5，不相等。这条根→叶路走不通，下一步要回溯：退回上一个分叉，把刚加的减掉，换另一条岔路再试。
回溯 · 离开 7：节点 7 这一侧已经探完（没有满足的路径），回溯：把它从当前路径弹出、累加和减回 20，并标蓝表示「这块走过了」。回到节点 11，换它的另一条岔路继续试。
走到节点 2 · 叶子：沿着路径往下走，踏上叶子节点 2，把它加进累加和：现在这条根→叶路径之和是 22。没有孩子了，下一步就看这个和等不等于目标 22。
命中！22 = 22：到叶子了，比对：这条路径 5+4+11+2 = 22，正好等于目标 22！找到一条满足的根→叶路径，答案就是 存在(true)，整棵树标绿这条路。
回溯 · 离开 2：节点 2 这条命中路径已确认，回溯：把它从当前路径弹出、累加和减回 20，并标蓝表示「这块走过了」。回到节点 11，继续演示完整 DFS、看它的另一条岔路。
回溯 · 离开 11：节点 11 的两侧都探完了，其中右叶子 2 已命中，回溯：把它从当前路径弹出、累加和减回 9，并标蓝表示「这块走过了」。回到节点 4，继续演示完整 DFS。
走到节点 9 · 叶子：沿着路径往下走，踏上叶子节点 9，把它加进累加和：现在这条根→叶路径之和是 18。没有孩子了，下一步就看这个和等不等于目标 22。
不中：18 ≠ 22：到叶子了，比对：这条路径之和 18，离目标 22 还差 4，不相等。这条根→叶路走不通，下一步要回溯：退回上一个分叉，把刚加的减掉，换另一条岔路再试。
回溯 · 离开 9：节点 9 这一侧已经探完（没有满足的路径），回溯：把它从当前路径弹出、累加和减回 9，并标蓝表示「这块走过了」。回到节点 4，换它的另一条岔路继续试。
回溯 · 离开 4：节点 4 这一侧探完了，左支里已经有命中路径，回溯：把它从当前路径弹出、累加和减回 5，并标蓝表示「这块走过了」。回到节点 5，继续演示完整 DFS、看它的右支。
走到节点 8：深度优先往下走，踏上节点 8，累加和变成 13（距目标 22 还差 9）。它还有孩子，把它留在当前路径上(绿)，继续往下深入——先走左子树。
走到节点 13 · 叶子：沿着路径往下走，踏上叶子节点 13，把它加进累加和：现在这条根→叶路径之和是 26。没有孩子了，下一步就看这个和等不等于目标 22。
不中：26 ≠ 22：到叶子了，比对：这条路径之和 26，离目标 22 还差 -4，不相等。这条根→叶路走不通，下一步要回溯：退回上一个分叉，把刚加的减掉，换另一条岔路再试。
回溯 · 离开 13：节点 13 这一侧已经探完（没有满足的路径），回溯：把它从当前路径弹出、累加和减回 13，并标蓝表示「这块走过了」。回到节点 8，换它的另一条岔路继续试。
走到节点 4：深度优先往下走，踏上节点 4，累加和变成 17（距目标 22 还差 5）。它还有孩子，把它留在当前路径上(绿)，继续往下深入——先走左子树。
走到节点 1 · 叶子：沿着路径往下走，踏上叶子节点 1，把它加进累加和：现在这条根→叶路径之和是 18。没有孩子了，下一步就看这个和等不等于目标 22。
不中：18 ≠ 22：到叶子了，比对：这条路径之和 18，离目标 22 还差 4，不相等。这条根→叶路走不通，下一步要回溯：退回上一个分叉，把刚加的减掉，换另一条岔路再试。
回溯 · 离开 1：节点 1 这一侧已经探完（没有满足的路径），回溯：把它从当前路径弹出、累加和减回 17，并标蓝表示「这块走过了」。回到节点 4，换它的另一条岔路继续试。
回溯 · 离开 4：节点 4 这一侧已经探完（没有满足的路径），回溯：把它从当前路径弹出、累加和减回 13，并标蓝表示「这块走过了」。回到节点 8，换它的另一条岔路继续试。
回溯 · 离开 8：节点 8 这一侧已经探完（没有满足的路径），回溯：把它从当前路径弹出、累加和减回 5，并标蓝表示「这块走过了」。回到节点 5，换它的另一条岔路继续试。
回溯 · 离开 5：根节点 5 的所有分支都探完了，此前已经找到命中路径，回溯：把它从当前路径弹出、累加和减回 0，并标蓝表示「这块走过了」。整棵树 DFS 结束。
答案 · 存在路径 = true：回到全局：在所有根→叶路径里，5→4→11→2 这条的和是 22，正好等于目标 22。所以答案是 存在(true)。只要找到一条命中就够了，不必把所有路径都走完。
参考代码
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); }}复杂度
- 时间：O(n)，最坏每个节点访问一次
- 空间：O(h)，递归栈深 = 树高 h；最坏(链)O(n)，平衡 O(log n)
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
翻转二叉树
LeetCode 226 · 简单 · 沿着 二叉树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题