题目描述

[EN | CN]

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

示例:

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

输出: [1,3,2]

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

解法 1:递归

树的结构太规律了,显然递归更加好写一些。中序遍历的顺序是 -> ->

假设一共 $n$ 个结点,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(\log n)$,由于递归需要压栈,栈的最大高度为树的深度,而二叉树的深度则可以归为 $\log n$。

实现与结果如下:

 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 inorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        ret = self.inorderTraversal(root.left)
        ret.append(root.val)
        ret.extend(self.inorderTraversal(root.right))
        return ret
  • 执行用时:32 ms,在所有 Python3 提交中击败了 84.52% 的用户。
  • 内存消耗:13.6 MB,在所有 Python3 提交中击败了 5.24% 的用户。

解法 2:迭代

有一种有点蠢的方法来将递归改为迭代,就是自己 手动维护一个栈,遍历的时候先往左子结点不断深入,每进入一次左子结点就把当前结点压栈,出来的时候再遍历自身,然后右子结点,直到清空整个栈。

时间复杂度和空间复杂度同递归方法。

实现与结果如下:

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

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack, ret, curr = [], [], root

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

        return ret
  • 执行用时:28 ms,在所有 Python3 提交中击败了 94.90% 的用户。
  • 内存消耗:13.5 MB,在所有 Python3 提交中击败了 5.24% 的用户。