105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode） (leetcode-cn.com)
public class BuildTree {
static HashMapmap =new HashMap<>();//标记中序遍历
static int[]preorder;//保留的先序遍历
public TreeNodebuildTree(int[] preorder, int[] inorder) {
if(preorder.length==0||inorder.length==0)
return null;
this.preorder = preorder;
for (int i =0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return recursive(0,0,inorder.length-1);
}
/**
* @param pre_root_idx 先序遍历的索引(当前根节点)
* @param in_left_idx 中序遍历的索引(当前二叉树在中序遍历中的左边界)
* @param in_right_idx 中序遍历的索引(当前二叉树在中序遍历中的右边界)
*/
public static TreeNoderecursive(int pre_root_idx, int in_left_idx, int in_right_idx) {
if(in_left_idx>in_right_idx)
return null;
//获取当前根节点
TreeNode root =new TreeNode(preorder[pre_root_idx]);
// 在中序中获当前根的索引
int idx =map.get(preorder[pre_root_idx]);
//当前左子树的根节点就是前序遍历第一个，就是pre_root_idx+1,左边边界就是in_left_idx，右边边界是当前根的索引-1
root.left =recursive(pre_root_idx+1,in_left_idx,idx-1);
//当前右子树的根，就是右子树（前序遍历）的第一个,就是当前根节点+当前左子树的数量
// pre_root_idx 当前的根 左子树的长度 = 左子树的左边-右边 (idx-1 - in_left_idx +1) 。最后+1就是右子树的根了
root.right =recursive(pre_root_idx + (idx-1 - in_left_idx +1) +1, idx +1, in_right_idx);
return root;
}
}
