145. Binary Tree Postorder Traversal

Loading...LeetCode

做Q106的时候就利用过postorder的这个性质：

postorder本质就是逆序版的right-first preorder

106. Construct Binary Tree from Inorder and Postorder Traversal

所以讨巧写法就是写个right-first preorder然后 reverse 就行。

或者按照recursively来写，也挺简单的。

麻烦的是iteratively地写，需要给 node 标记visited state，因为本质上是遍历了两遍tree，第一遍排出traversal order，第二遍获取值。

reversed right-first preorder

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        if not root: return res
        stack = collections.deque([root])
        while stack:
            cur = stack.pop()
            res.append(cur.val)
            if cur.left: stack.append(cur.left)
            if cur.right: stack.append(cur.right)
        res.reverse()
        return res

recursively

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        
        def postorder(node, res):
            if not node: return
            if node.left: postorder(node.left, res)
            if node.right: postorder(node.right, res)
            res.append(node.val)
        
        postorder(root, res)
        return res

iteratively

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        if not root: return res
        
        stack = collections.deque([(root, False)])
        while stack:
            node, visited = stack.pop()
            if visited: res.append(node.val)
            else:
                stack.append((node, True))
                if node.right: stack.append((node.right, False))
                if node.left: stack.append((node.left, False))

        return res