下楼吃个饭的功夫，就被辞退了

这年头，工作真是一出门就充满变数。前两天刷到个帖子，说一个哥们儿下楼吃个饭的功夫，回来就被辞退了。

我一开始还不信，直到看到评论区的网友更狠——“在外面给美的做宣传还领奖，回来账号直接被删”。资本啊，真是把人整明白了。

说实话，我作为个写Python的，也不是没遇到过类似的事儿。上个月，领导私下找我喝了杯咖啡，聊着聊着就开始画饼，话里话外感觉今年绩效堪忧。我心里有点数，这饼一画，裁员八成就排上日程了。

这种事，真是防不胜防。劳动法在那儿摆着，资本照样翻花样。朋友们，提前备份代码，刷刷题，简历也别落灰了，毕竟谁也不知道下一顿饭回来会不会还在工位上。

这道题的意思其实很直白：给你一棵二叉树，问从根节点到叶子节点，是否存在一条路径，使得路径上所有节点的值相加，正好等于给定的目标值。

第一次看这题，很多人可能会想用个栈、记录路径啥的，其实不需要搞那么复杂。它本质上就是个典型的递归问题，思路清晰了，代码就不难。

我写算法题一向是从“自顶向下”的思路入手，尤其是树的题目。你要干的事情就是在每个节点，去看看目标值减掉当前节点值后，剩下的能不能在子树里找到满足条件的路径。直到最后，找到叶子节点，看值是不是正好抵消完。

上代码，才是程序员表达思想的最好方式：

defhasPathSum(root, targetSum):
ifnot root:
returnFalse
ifnot root.left andnot root.right:
return targetSum == root.val
return (hasPathSum(root.left, targetSum - root.val) or
            hasPathSum(root.right, targetSum - root.val))

这个写法很Pythonic，也很简单。每次递归，我就把目标值减去当前节点值，然后递归左右子树。如果到了叶子节点，直接判断剩下的目标值是不是和当前节点值相等，符合就返回True。

左右子树只要有一个满足条件就行。这种写法的精髓在于：你不用去手动维护什么路径栈，递归的调用栈天然帮你搞定了。

当然，如果非得搞个栈、用迭代写，也是可以的，反正面试官有时候就爱看你不一样的解法。我之前有次面试，写递归写得飞快，面试官偏偏让我再用迭代写一遍。那行，咱上：

defhasPathSum(root, targetSum):
ifnot root:
returnFalse
    stack = [(root, root.val)]
while stack:
        node, curr_sum = stack.pop()
ifnot node.left andnot node.right and curr_sum == targetSum:
returnTrue
if node.right:
            stack.append((node.right, curr_sum + node.right.val))
if node.left:
            stack.append((node.left, curr_sum + node.left.val))
returnFalse

这种写法就跟以前咱写BFS差不多，自己手动维护一个栈，把节点和当前路径的和一起存进去。

每次弹出一个节点，就判断是不是叶子节点，而且路径和是不是目标值。没达到就把左右子节点塞进去，路径和也更新。其实这种写法能让你更直观地感受到递归和迭代在做同样的事。

说到底，这种题考的就是你对树的理解，还有对递归和迭代的掌握。很多初学者一看到树就头大，觉得好像很抽象。

但其实树这种结构，跟我们代码的调用栈非常像，递归本身就像一棵隐形的树在执行。写多了，你会发现，树这种数据结构真的是无处不在，不管是数据库的索引，还是前端页面的DOM树，理解它，真的能帮你在很多地方开窍。