Problem description:

Given the root of a binary tree, return the postorder traversal of its nodes’ values.

Input: root = [1,null,2,3]
Output: [3,2,1]

Solution:

We could use iterative and recursive to solve this question. Recursive it straight-forward, so I’ll just write the iterative one.

The idea is to notice each node would be visit twice when it needs to be print out. First time when the node is pass by parent, second time is when the node passing it’s child into stack. When the node got visited twice(marked as True), we could print it out. 

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, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stk, res = deque([(root, False)]), []
        while stk:
            node, visited = stk.pop()
            if visited:
                res.append(node.val)
            else: # LIFO so append left last
                stk.append((node, True))
                if node.right:
                    stk.append((node.right, False))
                if node.left:
                    stk.append((node.left, False))
        return res

time complexity: $O()$
space complexity: $O()$
reference:
related problem: