# 105. Construct Binary Tree from Preorder and Inorder Traversal 从前序与中序遍历序列构造二叉树

@TOC

## # 题目描述

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

Note: You may assume that duplicates do not exist in the tree.

For example, given

``````preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
``````

Return the following binary tree:

``````    3
/ \
9  20
/  \
15   7
``````

## # 解题方法

### # 递归

Python代码如下：

``````# 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 or not inorder:
return None
root = TreeNode(preorder[0])
index = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:index+1], inorder[:index])
root.right = self.buildTree(preorder[index+1:], inorder[index+1:])
return root
``````

## # 日期

2018 年 6 月 22 日 —— 这周的糟心事终于完了 2019 年 1 月 8 日 —— 别熬夜，我都开始有黑眼圈了。。 2020 年 5 月 22 日 —— 这天的每日一题，熬夜写题解，也会黑眼圈。