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``````

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/#/description

Given inorder and postorder traversal of a tree, construct the binary tree.