说明：
给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的前序遍历，inorder 是同一棵树的中序遍历，构造并返回二叉树。
输入：preorder = [3,9,20,15,7]，inorder = [9,3,15,20,7]
输出：[3,9,20,null,null,15,7]
解析：
1.递归思想
2.前序遍历：根结点 ---> 左子树 ---> 右子树
3.中序遍历：左子树--->?根结点?---> 右子树
4.后序遍历：左子树 ---> 右子树?---> 根结点
例如：
前序遍历：1 ?2 ?4 ?5 ?7 ?8 ?3 ?6
中序遍历：4 ?2 ?7 ?5 ?8 ?1 ?3 ?6
后序遍历：4 ?7 ?8 ?5 ?2 ?6 ?3 ?1?
-----------------------------------------------------------------------------------------------------
输入的preorder = [1,2,4,7,3,5,6,8] , inorder =[4,7,2,1,5,3,8,6]
代码：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回构造的TreeNode根节点
def __init__(self):
pass
def reConstructBinaryTree(self, pre, tin):
# write code here
if len(pre) == 0:
return None
if len(pre) == 1:
return TreeNode(pre[0])
else:
res = TreeNode(pre[0])
res.left = self.reConstructBinaryTree(pre[1: tin.index(pre[0]) + 1], tin[: tin.index(pre[0])])
res.right = self.reConstructBinaryTree(pre[tin.index(pre[0]) + 1: ], tin[tin.index(pre[0]) + 1: ])
return res
front = [1,2,4,7,3,5,6,8]
mid = [4,7,2,1,5,3,8,6]
algo = Solution()
x = algo.reConstructBinaryTree(pre=front , tin=mid)
代码流程：
front = [1,2,4,7,3,5,6,8]
mid = [4,7,2,1,5,3,8,6]
-------
1-node = 1 , index = mid.index(1) = 3
res.left = (pre = [2,4,7] , tin = [4,7,2])
2-node = 2 ,index = tin.index(2) = 2
res.left = (pre = [4,7] , tin = [4,7])
3-node = 4 , index = tin.index(4) = 0
res.left = (pre = [] , tin = [])
res.right = (pre = [7] , tin = [7])
node-right = 7
res.right = (pre = [] , tin = [])
res.right = (pre = [3,5,6,8] , tin = [5,3,8,6])
4-node = 3 , index = tin.index(3) = 1
res.left = (pre = [5] , tin =[5])
node = 5
res.right = (pre = [6 , 8] , tin=[8,6])
5-node = 6 , index = tin.index(6) = 1
res.left = (pre = [8] , tin = [8])
node-left = 8
res.right = (pre = [] , tin = [])最终的二叉树如下：?
?