Question: https://oj.leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
Question Name: Construct Binary Tree from Inorder and 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 42 43 44 45 46 47 48 49 50 51 52 53 54 | # Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param inorder, a list of integers # @param inOrderZone, an array to limit the nodes for current subtree # inOrderZone[0] is the beginning position of current subtree # in inorder array. inOrderZone[1] is the end position. # @param inPos, a dictionary with the position of each char in inorder. # @param postorder, a list of integers # @param postOrderZone, an array to limit the nodes for current subtree. # Same as inOrderZone. # @param postPos, a dictionary with the position of each char in postorder. # @return a tree node def buildTreeHelper(self, inorder, inOrderZone, inPos, postorder, postOrderZone, postPos): ''' Built the tree recuisively. The last element in postOrderZone array will always be the root of current tree (or subtree). ''' # Reach the leaf. if inOrderZone[1] < inOrderZone[0] : return None # Create the root node of current (sub)tree # The root node is in some middle place among inOrderZone. # The root node is in the last position of current postOrderZone. root = TreeNode(postorder[postOrderZone[1]]) # Recursively build the left son of current root leftInOrderZone = [inOrderZone[0], inPos[root.val]-1] leftCount = inPos[root.val] - inOrderZone[0] leftPostOrderZone = [postOrderZone[0], postOrderZone[0]+leftCount-1] root.left = self.buildTreeHelper(inorder, leftInOrderZone, inPos, postorder, leftPostOrderZone, postPos) # Recursively build the right son of current root rightInOrderZone = [inPos[root.val]+1, inOrderZone[1]] rightCount = inOrderZone[1] - inPos[root.val] rightPostOrderZone = [postOrderZone[1]-rightCount, postOrderZone[1]-1] root.right = self.buildTreeHelper(inorder, rightInOrderZone, inPos, postorder, rightPostOrderZone, postPos) return root # @param inorder, a list of integers # @param postorder, a list of integers # @return a tree node def buildTree(self, inorder, postorder): # There is not duplicate in the tree. And we record the position for # each charater in the inorder array and postorder array. inPos = {} postPos = {} for index in xrange(len(inorder)): inPos[inorder[index]] = index postPos[postorder[index]] = index return self.buildTreeHelper(inorder, [0, len(inorder)-1], inPos, postorder, [0, len(postorder)-1], postPos) |