题目描述

[EN | CN]

给定一个二叉树,返回它的 前序遍历

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,2,3]

进阶:递归算法很简单,你可以通过迭代算法完成吗?

解法 1:递归

思路与复杂度分析都参考《LeetCode 094. 二叉树的中序遍历》(本博客)。

实现与结果如下:

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

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        ret = [root.val]
        ret.extend(self.preorderTraversal(root.left))
        ret.extend(self.preorderTraversal(root.right))
        return ret
  • 执行用时:28 ms,在所有 Python3 提交中击败了 95.10% 的用户。
  • 内存消耗:13.7 MB, 在所有 Python3 提交中击败了 5.54% 的用户。

解法 2:迭代

思路与复杂度分析都参考《LeetCode 094. 二叉树的中序遍历》。

实现与结果如下:

 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 preorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        ret = []
        curr = root

        while curr is not None or len(stack) > 0:
            while curr is not None:
                ret.append(curr.val)
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            curr = curr.right

        return ret
  • 执行用时:48 ms,在所有 Python3 提交中击败了 20.38% 的用户。
  • 内存消耗:13.3 MB,在所有 Python3 提交中击败了 5.54% 的用户。