题目描述
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例1
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例2
Input: preorder = [-1], inorder = [-1] Output: [-1]
做题思路
1.前序遍历的首元素为树的根节点root值
2.在中序遍历中搜索根节点root的索引，可将中序遍历划分为左子树|根|右子树
3.根据中序遍历中的左（右）子树的节点数量，可将前序遍历划分为根|左子树|右子树
以此来确定树的根节点、左子树根节点和右子树根节点
分治算法剖析
1.递推参数
pre_root（根节点在前序遍历的索引）
in_left（子树在中序遍历的左边界）
in_right（子树在中序遍历的右边界）
2.终止条件
in_left>in_right（已经越过叶节点）
3.递推过程
（1）根节点root=preorder[pre_root]
（2）划分左右子树：查找根节点在中序遍历inorder中的索引
（3）构建左右子树：开启左右子树递归
4.返回root
代码
class Solution {
int[] preorder;//保存前序遍历，在递归时依据索引访问前序遍历的值
HashMap hashMap=new HashMap<>();//标记中序遍历
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder=preorder;
//将中序遍历的值及索引放进map，在递归时获取左子树与右子树的数量以及根的索引
for(int i=0;iin_right){
return null;
}
TreeNode root=new TreeNode(preorder[pre_root]);//获取根节点
int index=hashMap.get(preorder[pre_root]);//获取中序遍历根节点所在索引以获取左子树数量
//左子树根索引为前序遍历根节点索引+1
//递归左子树左边界为原本中序遍历左边界
//递归左子树右边界为中序遍历根节点索引-1
root.left=recur(pre_root+1,in_left,index-1);
//右子树根索引为前序遍历的当前根节点索引+左子树节点的数量+1
//递归右子树左边界为中序遍历根节点索引+1
//递归右子树右边界为中序遍历右边界
root.right=recur(pre_root+index-in_left+1,index+1,in_right);
return root;
}
} 
