Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
return self.create_tree(inorder, 0, len(inorder) -1 , postorder, 0, len(postorder) - 1)
def search_divindex(self, inorder, low_inorder, high_inorder, val):
for i in range(low_inorder, high_inorder+1):
if inorder[i] == val:
return i
return -1
def create_tree(self, inorder, low_inorder, high_inorder, postorder, low_postorder, high_postorder):
if (low_inorder > high_inorder) or (low_postorder > high_postorder):
return None
root = TreeNode(postorder[high_postorder])
div_index = self.search_divindex(inorder, low_inorder, high_inorder, root.val)
size_left_subtree = div_index - low_inorder
size_right_subtree = high_inorder - div_index
root.right = self.create_tree(inorder, div_index + 1, high_inorder, postorder,
high_postorder - size_right_subtree, high_postorder - 1)
root.left = self.create_tree(inorder, low_inorder, div_index - 1,
postorder,
high_postorder - size_right_subtree - size_left_subtree,
high_postorder - size_right_subtree - 1)
return root