最开始我想到的是沿着一条路走下去，走到头发现不等于sum的时候，就倒退，把数值减回去，但是我想了很久没想到怎么写。
后来干脆试试自底而上的方式，就是先到最底下的节点，然后往上加，但没想到该如何设置返回。
最后用暴露法，就深度遍历，把当前节点的和传下去，只要有叶子节点求和等于sum，返回True，递归函数在回调的时候，如果收到下层的返回值为True，那就直接返回True。
class Solution: def hasPathSum(self, root: TreeNode, sum: int) -> bool: if not root: return False self.sum = sum def walk(p, num): num1 = p.val + num if not any((p.left, p.right)): if num1 == self.sum: return True else: if p.left: num2 = walk(p.left, num1) if num2: return True if p.right: num3 = walk(p.right, num1) if num3: return True res = walk(root, 0) if res: return True elif res == None: return False结果发现效率还行。另外，我最开始想到的思路，应该是空间复杂度很小的，时间复杂度相同。自底而上的方式我总感觉在哪看到过。看来题目还是需要回顾一下，虽然是简答题。
另外一种使用迭代和栈实现深度优先遍历。思路就是像传递层深度一样，传递当前节点到根节点的和值。当找到叶子节点了，判断值和sum的关系，当不是叶子节点，继续向下传递。
class Solution: def hasPathSum(self, root: TreeNode, sum: int) -> bool: if not root: return False self.sum = sum stack = [(root, 0)] while stack: p, num = stack.pop() num += p.val if not any([p.left, p.right]): if num == self.sum: return True if p.left: stack.append([p.left, num]) if p.right: stack.append([p.right, num]) return False