# 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
Given inorder and postorder traversal of a tree, construct the binary tree.