题目描述

[EN | CN]

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

示例:

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

输出: [3,2,1]

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

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

解法 2:迭代 + 标记

与前序遍历、中序遍历相比,后续遍历的迭代写法更难一些。原因在于前两者利用栈来存储之后需要处理的结点,当出栈时可以随便出栈,不需要考虑太多;而对于后序遍历来说,考虑出栈的时候却要有两种情况:

  1. 可能刚遍历完左子结点,右子结点还未遍历,此时应该进入右子结点,当前结点应该保留在栈中(遍历完右子结点还要用到该结点的值);
  2. 可能左子结点和右子结点都遍历完了,此时应该使用该结点的值,然后出栈。

为了分辨任一结点的右子结点是否已经被遍历过了,我们可以引入额外的数组来标记该结点的右子结点是否已经被遍历(也可以标记该结点已经被访问的次数等)。当出栈的时候:

  • 如果栈顶结点未被访问,则不出栈,将栈顶结点标记为「已访问」,访问该栈顶结点的右子结点;
  • 如果栈顶结点已被访问,则出栈,输出该结点的值,再将当前指针设置为 None(目的是防止下轮迭代的时候以为该结点从未被遍历过,然后又从这里开始 DFS,无限循环)。

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

  • 时间复杂度为 $O(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
23
24
25
26
27
28
29
30
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

        while curr is not None or len(stack) > 0:
            while curr is not None:
                stack.append(curr)
                visited.append(False)
                curr = curr.left
            curr = stack[-1]
            if visited[-1]:  # Visited
                stack.pop()
                visited.pop()
                ret.append(curr.val)
                curr = None
            else:  # Not visited
                curr = curr.right
                visited[-1] = True

        return ret
  • Runtime: 32 ms, faster than 93.23% of Python3 online submissions for Binary Tree Postorder Traversal.
  • Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Binary Tree Postorder Traversal.
  • 执行用时:36 ms,在所有 Python3 提交中击败了 66.45% 的用户。
  • 内存消耗:13.5 MB,在所有 Python3 提交中击败了 5.83% 的用户。