Description
Given a binary tree, return the postorder traversal of its nodes’ values. Here the inorder means [left right root]. LeetCode here.
Recusive Solution
It’s quite easy, we jump to the code.
def postorder_rec(Node):
output = []
def helper(Node):
if Node.left:
helper(Node.left)
if Node.right:
helper(Node.right)
output.append(Node.val)
helper(Node)
return output
Iterative Solution
Now we need a stack to save traversed nodes. The nodes in the stack should satisfy the following conditions:
- The left child of the node has benn traversed.
- The value of the node has not been saved.
Note that the current node is always the child of the last node in the stack. step 1: Go through the left child until it donot have left child. And now we have two situation:
step 2:
- have right child go to right child and go to step 1
- no right child
- current node is left child and have sibling go to sibling and go to step 1
- else go to father and go to step 2
Finally, when should we stop? Similart to inorder search, if and only if the stack is empty and current node has no right child.
def postorder(Node):
if not Node:
return []
output = []
Now = Node
traveled = [Now]
while True:
while Now.left:
Now = Now.left
traveled.append(Now)
if Now.right:
Now = Now.right
traveled.append(Now)
else:
while True:
try:
traveled.pop(-1)
output.append(Now.val)
father = traveled[-1]
if Now == father.left and father.right:
Now = father.right
traveled.append(Now)
break
else:
Now = father
except IndexError:
return output
Similart question: LeetCode 94 Binary Tree Inorder Traversal