Question: https://oj.leetcode.com/problems/binary-tree-postorder-traversal/
Question Name: Binary Tree Postorder Traversal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | # Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @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. stackReady.append(current) # 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: result.append(stackReady.pop().val) return result |