二叉树的所有路径

🟢 Easy · 🏷️ 树、DFS、字符串、回溯 · LeetCode#257

📖 题目

返回一棵二叉树所有从根节点到叶子节点的路径（叶子节点=没有子节点的节点），顺序不限。

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

💡 思路

DFS 一路走一路拼路径字符串：每到一个节点就把它的值接到 path 后面，走到叶子节点就把当前 path 存进结果，否则继续往左右子树递归，递归前先补上 "->" 分隔符。

为什么不用显式回溯：字符串在 Python 里是不可变对象，path += str(node.val) 每次都会创建一个新字符串，不会修改调用者手里的那份——左子树递归改的 path，不会影响右子树递归拿到的 path，天然不会串味，不需要像操作列表那样手动 pop() 撤销。

💻 代码

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        result = []

        def dfs(node: Optional[TreeNode], path: str):
            if not node:
                return
            path += str(node.val)
            if not node.left and not node.right:   # 叶子节点，收尾
                result.append(path)
            else:
                path += "->"
                dfs(node.left, path)
                dfs(node.right, path)

        dfs(root, "")
        return result

时间复杂度 O(n)，空间复杂度 O(h)（不计结果数组），h 是树高。