技术大牛朋友，年包大概80万，为了冲刺百万年薪，他去竞聘了Team Leader，工作半年下面人不服他，领导觉得他能力不行

那天晚上在公司加班，隔壁小同学突然冲过来一句：“东哥，这个路径总和你帮我看一下呗，我脑子已经成 json 了…” 我一看题目：哦，老朋友了，就是那个二叉树里找一条从根走到叶子，节点值加起来刚好等于 target 的玩意儿。

你可以脑补成这么个场景哈：你从公司大门口（root）往各种工位绕，路过每个同事都要被摸一次钱（节点值），走到工位尽头（叶子节点），看兜里钱是不是刚好等于 target。只要有一条路金额对上了，题目就说 “True”，否则就是 “False”。

当时那小子写的版本是这样思路： “我把所有根到叶子的路径都搞出来，存个二维数组，然后一个个算和。” 听着也没毛病，就是…有点上纲上线，树稍微大一点，内存分分钟干碎。

我就跟他说，别折腾那个大数组了，这题就是个 DFS+回溯里最温柔的一种：你一路往下走，一路把 target 往下减，走到叶子那一刻，看剩下的是不是 0，0 就成功，非 0 就继续回去瞎逛。

先丢个最朴素的 Python 树节点定义，那天我就是在白板上这么给他画的：

classTreeNode:
def__init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

然后核心逻辑，实际上就几行，但坑点一堆，那天他就被一个小细节坑了半小时，跟我之前排查 MySQL 主从同步那个诡异 relay log 损坏差不多味道：

classSolution:
defhasPathSum(self, root: TreeNode | None, targetSum: int) -> bool:
# 空树直接灭
ifnot root:
returnFalse

defdfs(node: TreeNode, remain: int) -> bool:
# 走到当前节点，把它的值扣掉
            remain -= node.val

# 关键点：必须是“叶子 + remain == 0”才算一条完整路径
ifnot node.left andnot node.right:
return remain == 0

# 往左子树试试
if node.left and dfs(node.left, remain):
returnTrue

# 往右子树试试
if node.right and dfs(node.right, remain):
returnTrue

# 左右都不行，就让上一层继续找
returnFalse

return dfs(root, targetSum)

他那会儿的 bug 在哪？ 他只检查了 remain == 0，没管是不是叶子。结果有一种诡异情况： 路径还没走到底，先中途凑巧减成 0 了，他就直接 True 了…就跟你银行还房贷还一半，余额正好为 0，你说“哎呀这期还完了”，银行说“兄弟你先别激动，还有 20 年呢”。

所以这个判断一定要是：

ifnot node.left andnot node.right and remain == 0:
returnTrue

要么就像上面的写法那样，先判断叶子，再比较 remain。

再有一个小细节，就是很多人会写成这种一眼看上去挺“pythonic”的：

classSolution:
defhasPathSum(self, root: TreeNode | None, targetSum: int) -> bool:
ifnot root:
returnFalse

# 叶子直接判断
ifnot root.left andnot root.right:
return root.val == targetSum

        new_target = targetSum - root.val
return (self.hasPathSum(root.left, new_target) or
                self.hasPathSum(root.right, new_target))

这个写法其实也 OK，而且更短，就是要注意那个 or，别写成了 and。 我有次面试的时候就遇到一个哥们，嘴里说“只要有一条路径就可以”，代码里写的是 and，当场自爆。

复杂度这块，顺嘴说一下就行： 树里每个节点最多被访问一次，所以时间是 O(n)，n 是节点数。空间呢，如果不算递归栈就 O(1)，算的话是 O(h)，h 是树的高度，最差那种链表树就是 O(n)。一般面试官听到你能提到“递归深度”和“最坏退化成链表”这种词，就会点点头：嗯，这人至少看过点源码，不是刚从短视频里学来的。

再往后玩的话，这个题其实有一堆变形，比如：

• 不问 True/False，问你有几条这样的路径
• 让你把所有满足条件的路径都返回出来，变成 List[List[int]]
• 甚至把树换成图，路径上不能重复节点之类的

套路都一样，DFS+回溯，区别就是你要不要额外维护一个 path 数组，把路上走过的值顺手记一下：

defdfs(node, remain, path, ans):
ifnot node:
return

    path.append(node.val)
    remain -= node.val

ifnot node.left andnot node.right and remain == 0:
        ans.append(path[:])  # 注意拷贝

    dfs(node.left, remain, path, ans)
    dfs(node.right, remain, path, ans)

# 回来的时候把最后一个弹掉，典型回溯动作
    path.pop()

这个 path.pop() 不写，你后面 debug 的时候，看到数组一路长成长龙，整个人就会有种“我到底在干嘛”的迷茫感，跟看 TCP 抓包里一堆 0x1234abcd 差不多窒息。

行，差不多就这样，你先把这个版本敲一遍，自己画两棵小树手算一下，看代码流程和你脑子里的走路路径是不是对得上。 我去泡个咖啡，你要是把这题写成层序遍历配前缀和那种花里胡哨的写法，记得截个图发我乐呵一下。