6/22/2017 - 3:40 AM

## 105. Construct Binary Tree from Preorder and Inorder Traversal

1. Construct Binary Tree from Preorder and Inorder Traversal
``````# In this solution, we use lenLeft to determine the left/right nodes in preorder,
# Rather than traverse it sequentially.

# 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, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if len(inorder) == 0:
return None
self.inDict = {}
for index,each in enumerate(inorder):
self.inDict[each] = index
# self.preIndex = 0
return self.build(inorder, 0, len(inorder) - 1, preorder, 0, len(preorder)-1)
def build(self, inorder, inStart, inEnd, preorder, preStart, preEnd):
if inStart > inEnd:
return None
curVal = preorder[preStart]
curInIndex = self.inDict[curVal]
leftLen = curInIndex - inStart
curNode = TreeNode(curVal)
# self.preIndex += 1
curNode.left = self.build(inorder,  inStart,      curInIndex-1, preorder, preStart+1,         preStart+leftLen)
curNode.right = self.build(inorder, curInIndex+1, inEnd,        preorder, preStart+1+leftLen, preEnd)
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, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if len(inorder) == 0:
return None
self.inDict = {}
for index,each in enumerate(inorder):
self.inDict[each] = index
self.preIndex = 0
return self.build(inorder, 0, len(inorder) - 1, preorder)
def build(self, inorder, inStart, inEnd, preorder):
# Like problem 106, we use inDict to determine the curInIndx and left/right nodes
if inStart > inEnd:
return None
curVal = preorder[self.preIndex]
curInIndex = self.inDict[curVal]
leftLen = curInIndex - inStart
curNode = TreeNode(curVal)
self.preIndex += 1
curNode.left = self.build(inorder,  inStart,      curInIndex-1, preorder)
curNode.right = self.build(inorder, curInIndex+1, inEnd,        preorder)
return curNode``````

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

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