Question Name: Binary Tree Postorder Traversal
Solution to Binary Tree Postorder Traversal by LeetCode
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# @param root, a tree node
# @return a list of integers
def postorderTraversal(self, root):
# Handle with the special cast (empty input)
if root == None: return 
# Every node will be accessed twice in the stacks.
# As post order traversal required:
# The first time, we will pop and check its son(s).
# The second time, we will check its value.
# So we are using two stacks here. One for the nodes to be accessed
# for the first time. The other is used for the nodes, waiting for
# the second access.
stackPrepare = [root]
stackReady = 
result = 
while len(stackPrepare) != 0 :
current = stackPrepare.pop()
# Current node is finally read after reading its son(s). So
# it is pushed firstly.
# The sons are going to travel tow stacks, which are FILO.
# We want to read left son first, if it exists.
# So we push the left son first. Please notice that, in the
# first stack, it would be left -> right
# When in the second stack, it would be root -> right -> left
# And final when reading the value into result, the order is:
# left -> right -> root, as post order traversal.
if current.left != None: stackPrepare.append(current.left)
if current.right != None: stackPrepare.append(current.right)
while len(stackReady) != 0: