moonlightshadow123
6/21/2017 - 3:20 PM

106. Construct Binary Tree from Inorder and Postorder Traversal

  1. Construct Binary Tree from Inorder and Postorder Traversal
# In this solution, we use LeftLen to determine the left/right nodes in postorder, rather than traverse it sequentiallly

# 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
        """
        if len(inorder) == 0 :
            return None
        self.inorderDict = {}
        for index, each in enumerate(inorder):
            self.inorderDict[each] = index
        # self.postIndex = len(inorder) - 1
        return self.build(inorder, 0, len(inorder)-1, postorder, 0, len(postorder)-1)
    def build(self, inorder, inStart, inEnd, postorder, postStart, postEnd):
        # We basically build the tree in postorder, 
        # but inorder, inStart, inEnd are here to determine the right nodes and left nodes of curNode.
        # Cause if you just give postorder, those can be confused.
        if inStart > inEnd:
            return None
        curVal = postorder[postEnd]
        curInIndex = self.inorderDict[curVal]
        leftLen = curInIndex - inStart
        curNode = TreeNode(curVal)
        # self.postIndex -= 1
        curNode.left = self.build(inorder,  inStart,      curInIndex-1, postorder, postStart,          postStart+leftLen-1)
        curNode.right = self.build(inorder, curInIndex+1, inEnd,        postorder, postStart+leftLen,  postEnd-1)
        return curNode
# 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
        """
        if len(inorder) == 0 :
            return None
        self.inorderDict = {}
        for index, each in enumerate(inorder):
            self.inorderDict[each] = index
        self.postIndex = len(inorder) - 1
        return self.build(inorder, 0, len(inorder)-1, postorder)
    def build(self, inorder, inStart, inEnd, postorder):
        # We basically build the tree in postorder, 
        # but inorder, inStart, inEnd are here to determine the right nodes and left nodes of curNode.
        # Cause if you just give postorder, those can be confused.
        if inStart > inEnd:
            return None
        curVal = postorder[self.postIndex]
        curInIndex = self.inorderDict[curVal]
        leftLen = curInIndex - inStart
        curNode = TreeNode(curVal)
        self.postIndex -= 1
        curNode.right = self.build(inorder, curInIndex+1, inEnd,        postorder)
        curNode.left = self.build(inorder,  inStart,      curInIndex-1, postorder)
        
        return curNode