目录

0257:二叉树的所有路径

力扣第 257 题

题目

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

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

示例 1:

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

示例 2:

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

提示:

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

相似问题:

分析

遍历时维护根节点到当前节点的路径,遇到叶子节点就加到结果中即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        def dfs(u):
            path.append(str(u.val))
            if not u.left and not u.right:
                res.append('->'.join(path))
            for v in [u.left,u.right]:
                if v:
                    dfs(v)
            path.pop()
        res,path = [],[]
        dfs(root)
        return res

26 ms