题目描述

[EN | CN]

给定一个二叉树,返回所有从根结点到叶子结点的路径。

说明:叶子结点是指没有子结点的结点。

示例:

1
2
3
4
5
6
7
8
输入:
   1
 /   \
2     3
 \
  5
输出: ["1->2->5", "1->3"]
解释: 所有根结点到叶子结点的路径为: 1->2->5, 1->3

解法 1:递归

假设结点数为 $n$,那么

  • 时间复杂度为 $O(n)$,所有结点都需要遍历一遍;
  • 空间复杂度这里如果不考虑存储 paths 的空间,那么平均为 $O(\log n)$,最坏为 $O(n)$,其实就是递归的深度。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

        def dfs(path, curr):
            if curr:
                path += str(curr.val)
                if curr.left or curr.right:
                    dfs(path + '->', curr.left)
                    dfs(path + '->', curr.right)
                else:
                    paths.append(path)

        paths = []
        dfs('', root)
        return paths
  • 执行用时:28 ms,在所有 Python3 提交中击败了 98.28% 的用户。
  • 内存消耗:13.5 MB,在所有 Python3 提交中击败了 7.14% 的用户。