145. Binary Tree Postorder Traversal

二叉搜索树后序遍历

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        # 6 star, 非递归版本，必须掌握
        # 后续遍历是先遍历左子树，后遍历右子树，最后才是根节点
        # 仍然使用栈，先将根节点入栈，然后入栈左子树和右子树，因为后进先出，
        # 所以实际顺序是右子树、左子树、根节点，最后将结果翻转即可
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            cur = stack.pop()
            result.append(cur.val)
            if cur.left:
                stack.append(cur.left)
            if cur.right:
                stack.append(cur.right)
        return result[::-1]