027 · Binary Tree Paths

algorithm

Published

June 2, 2026

My First Thoughts

这道题要返回所有从根到叶子的路径，所以第一反应很直接：得把整棵树遍历一遍，一条都不能漏。路径格式也很明确，每条路径是一个字符串，节点之间用 -> 连接。

先从 root 开始想。题目约束里节点数量是 [1, 100]，所以 root 不会是 None，一开始可以先不纠结空树。顺着一个节点往下看，无非三种情况：

如果左右都没有孩子，当前节点就是叶子，这条路径到此为止，结果只有当前这个值，str(root.val)。

如果只有一边有孩子，就把当前值接到那一边后面，像 root.val -> child.val。

如果两边都有孩子，就会分出两条方向，root.val -> 左边的路径 和 root.val -> 右边的路径。

到了下一个节点，要做的事情完全一样：判断它是不是叶子，不是就继续往下接。这种”每一层都重复同样动作”的结构，自然就想用递归来写。

按这个直觉写一版初稿，大概是这样：

def treepaths(root):
    path = str(root.val)

    if root.left is None and root.right is None:
        return path

    if root.left is not None:
        left_path = treepaths(root.left)
        path = path + "->" + left_path

    if root.right is not None:
        right_path = treepaths(root.right)
        path = str(root.val) + "->" + right_path

    return path

方向上有几点是对的：从根一路走到叶子、叶子是路径的终点、每经过一层就把当前值接到前面、左右子树会产生不同的路径。但写到这里就卡住了，最别扭的是那个 path 变量——它到底该装什么、左右分支会不会互相干扰，越想越不对劲。真正需要理顺的，其实是这个递归函数应该返回什么。

Why That Is Not Enough

初稿差在两个地方，而且都和”返回什么”有关。

第一个问题是返回的类型不统一。叶子节点那一支返回的是一个字符串 return path，但题目要的是”所有路径”，也就是一个字符串列表。哪怕整棵树只有一条路径，也应该返回 ["1"] 而不是 "1"。一个函数有时返回字符串、有时返回别的东西，调用它的父节点就没法统一处理。

第二个问题更要命：左右两条分支没能同时保留下来。初稿里只有一个 path 变量，走完左子树后它可能是 "1->2->5"，但只要右子树也存在，下面这行就会把它整个改写成右边的路径：

path = str(root.val) + "->" + right_path

左边那条路径就这么丢了。这说明一个节点下面可能挂着很多条根到叶子的路径，单个字符串根本装不下，返回值必须能容纳多条结果——也就是一个列表。

两个问题指向同一个结论：让递归函数始终返回一个路径列表。这样思路就顺了——先让子树告诉我”从孩子出发有哪些路径”，再把当前节点的值接到每条子路径前面。拼接本身在 Python 里很简单，str(root.val) + "->" + child_path 就够了。

Final Idea

关键的一步，是把递归函数的返回值重新定义清楚：

binaryTreePaths(root) 返回从当前节点 root 出发，到所有叶子节点的路径字符串列表。

举个小例子。对这棵树：

    2
     \
      5

从节点 2 出发应该返回 ["2->5"]；而从节点 5 出发，它自己就是叶子，返回 ["5"]。

返回值这么一定，每个节点要做的事情就清楚了：去左子树拿到它那边所有的路径，去右子树拿到它那边所有的路径，再把当前节点的值接到每一条子路径前面。按这个分工往下写。

先处理空节点。题目虽然保证至少有一个节点，但加上这一句，能让中间节点递归到”不存在的那一边”时自然得到空结果，省去单独判断左右孩子在不在：

if root is None:
    return []

空节点下面没有任何路径，所以返回空列表。

再处理叶子节点。叶子是一条完整路径的终点，从它出发只有一条路径，就是它自己：

if root.left is None and root.right is None:
    return [str(root.val)]

最后是中间节点。准备一个结果列表，把左右子树返回的每一条路径都接上当前节点的值，收集起来：

paths = []

for path in binaryTreePaths(root.left):
    paths.append(str(root.val) + "->" + path)

for path in binaryTreePaths(root.right):
    paths.append(str(root.val) + "->" + path)

return paths

这样就不用维护任何全局的路径变量，也不会出现左右分支互相覆盖的问题。每个递归调用只负责返回”从自己出发的所有路径”，父节点只负责在这些路径前面补上自己的值。前面初稿里卡住的两件事，到这里都化解了。

Why It Works

递归函数 binaryTreePaths(root) 的含义是：返回从当前节点 root 到所有叶子节点的路径字符串列表。三种情况各自对应递归的一种角色。

空节点下面没有任何路径，返回空列表。叶子节点是路径的终点，从它出发只有它自己这一条，返回 [str(root.val)]。中间节点则是个”汇总者”：经过它的完整路径，必然延续自左子树或右子树里的某一条，所以先递归拿到两边的全部路径，再把当前节点的值接到每一条前面。

因为每一条根到叶子的路径都会在它的叶子处生成，再被沿途每一层父节点逐级接上自己的值，所以最终汇总到根节点的，正好是整棵树所有的根到叶子路径，一条不多、一条不少。

Code

def binaryTreePaths(root):
    if root is None:
        return []

    if root.left is None and root.right is None:
        return [str(root.val)]

    paths = []

    for path in binaryTreePaths(root.left):
        paths.append(str(root.val) + "->" + path)

    for path in binaryTreePaths(root.right):
        paths.append(str(root.val) + "->" + path)

    return paths

Complexity

Time	\(O(nh)\) - 需要访问每个节点，拼接路径字符串时最多会复制长度为树高 `h` 的内容
Space	\(O(nh)\) - 返回结果本身可能包含多条长度为 `h` 的路径，递归调用栈额外需要 \(O(h)\)

Takeaway

递归题最重要的是先说清楚函数返回什么。这道题不要一开始就纠结怎么维护整条路径，可以反过来定义：每个节点返回“从自己出发的所有路径”。叶子节点返回一个只包含自己的列表，中间节点把自己的值接到子路径前面。返回值定义清楚以后，字符串拼接和左右分支就都会变得简单。

← Quiz