Given the root of a binary tree, return the postorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3] Output: [3,2,1]
Example 2:
Input: root = [] Output: []
Example 3:
Input: root = [1] Output: [1]
Constraints:
- The number of the nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
I'll show three way to approach the problem. 1. Using Two Stack
def post_order_tree_traversal_two_stack(self, root):
""" Post order tree traversal. """
if not root:
return root
stack1 = []
stack2 = []
stack1.append(root)
while stack1:
value = stack1.pop()
stack2.append(value.val)
if value.left:
stack1.append(value.left)
if value.right:
stack1.append(value.right)
stack2.reverse()
return stack2
- Recursive manner
def postorderTraversal(self, root):
""" Postorder Tree traversal with recursive function call. left -> right -> root """
if root:
self.postorderTraversal(root.left)
self.postorderTraversal(root.right)
self.result.append(root.val)
return self.result
- Iterative manner using one stack
def post_order_iterative(self, root):
""" Post-order tree traversal in iterative manner. """
stack = []
current = root
prev = None
while current or stack:
while current:
stack.append(current)
current = current.left
while not current and stack:
current = stack[-1]
if current.right == None or current.right == prev:
stack.pop()
self.result.append(current.val)
prev = current
current = None
else:
current =current.right
return self.result
A good resource can be found at Iterative traversals for Binary Trees