Binary Tree Postorder Traversal
franklinqin0 StackTreeMorris
# 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
1
2
3
4
5
2
3
4
5
# Solution
Let be the number of nodes in the tree.
# Recursion
Complexity
time:
space:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def postorder(node: TreeNode):
if not node: return
postorder(node.left)
postorder(node.right)
res.append(node.val)
postorder(root)
return res
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# Follow Up
Recursive solution is trivial, could you do it iteratively?
# Iteration
Complexity
time:
space:
# Two Stacks
From bottom to top, s1
stores root
, left subtree and right subtree, s2
stores root
and traverses the right subtree before the left subtree, res
reverses s2
and stores left subtree, right subtree and root
.
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root: return []
res = []
s1, s2 = [root], []
while s1:
node = s1.pop()
s2.append(node.val)
if node.left:
s1.append(node.left)
if node.right:
s1.append(node.right)
while s2:
res.append(s2.pop())
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# One Stack (REDO)
pre
stores the current node once the right subtree is done visiting.
Complexity
time:
space:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
pre = None
while root or stack:
# keep visiting the left subtree
while root:
stack.append(root)
root = root.left
root = stack.pop()
# right subtree is done visiting
if not root.right or root.right == pre:
res.append(root.val)
pre = root
root = None
# keep visiting the right subtree
else:
stack.append(root)
root = root.right
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21