根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
# 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 not preorder:
return None
root = TreeNode(preorder[0])
pos = inorder.index(root.val)
root.left = self.buildTree(preorder[1:pos+1], inorder[:pos])
root.right = self.buildTree(preorder[pos+1:],inorder[pos+1:])
return root
# 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
"""
def build_tree(prel, prer, pre, inl, inr, ino, pre_ino_map):
if prel > prer or inl > inr:
return
root = TreeNode(pre[prel])
pre_index = pre_ino_map[pre[prel]]
root.left = build_tree(prel + 1, prel + pre_index - inl, pre, inl, pre_index - 1, ino, pre_ino_map)
root.right = build_tree(prel + pre_index - inl + 1, prer, pre, pre_index + 1, inr, ino, pre_ino_map)
return root
ino_map = {}
for i in range(len(inorder)):
ino_map[inorder[i]] = i
root = build_tree(0, len(preorder) - 1, preorder, 0, len(inorder) - 1, inorder, ino_map)
return root
