What is the easiest way to track root-to-leaf paths in Binary Tree Paths?

Use depth-first search while maintaining the current path as a string, backtracking when returning from child nodes.

How do I handle leaf node detection to avoid missing paths?

Check that both left and right children are null before adding the current path to results to ensure only complete paths are stored.

Can I implement this problem iteratively instead of recursively?

Yes, by using a stack to store node-path pairs and popping nodes while extending paths, you can replicate DFS iteratively.

What are common mistakes when concatenating paths?

Forgetting to separate values with '->', or failing to backtrack the path string between branches, can corrupt output.

How does GhostInterview help with the binary-tree traversal and state tracking pattern?

It ensures that traversal state is properly maintained, paths are correctly added at leaves, and common backtracking errors are highlighted.

#257

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

二叉树的所有路径

给你一个二叉树的根节点 root ，按任意顺序，返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点。示例 1：输入： root = [1,2,3,null,5] 输出： ["1->2->5","1->3"] 示例 2：输入： root = [1] 输出： ["1"] 提示：…

字符串回溯树深度优先搜索二叉树

题目描述

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]
输出：["1"]

提示：

树中节点的数目在范围 [1, 100] 内
-100 <= Node.val <= 100

lightbulb

解题思路

方法一：DFS

我们可以使用深度优先搜索的方法遍历整棵二叉树，每一次我们将当前的节点添加到路径中。如果当前的节点是叶子节点，则我们将整个路径加入到答案中。否则我们继续递归遍历节点的孩子节点。最后当我们递归结束返回到当前节点时，我们需要将当前节点从路径中删除。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是二叉树的节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        def dfs(root: Optional[TreeNode]):
            if root is None:
                return
            t.append(str(root.val))
            if root.left is None and root.right is None:
                ans.append("->".join(t))
            else:
                dfs(root.left)
                dfs(root.right)
            t.pop()

        ans = []
        t = []
        dfs(root)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(N) since every node is visited once, and constructing the path strings can also take O(N) per path. Space complexity is O(H) for recursion or stack storage, where H is the tree height, plus additional space for result strings.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Pay attention to leaf node identification to avoid missing paths.
question_mark
Ensure string paths are constructed incrementally, not concatenated at the end only.
question_mark
Watch for off-by-one errors in backtracking or path formatting with '->'.

warning

常见陷阱

外企场景

error
Forgetting to backtrack when returning from recursion, leading to corrupted paths.
error
Incorrectly identifying leaf nodes, which may skip paths or add incomplete strings.
error
Using global or shared path state without copying, causing multiple paths to overlap incorrectly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return paths in reversed order or sorted lexicographically.
arrow_right_alt
Generate paths as arrays of integers instead of string representations.
arrow_right_alt
Handle trees where nodes may contain duplicate values but still track unique paths.

help

常见问题

外企场景

继续练习

#988 从叶结点开始的最小字符串 #297 二叉树的序列化与反序列化 #113 路径总和 II