package test;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * @author dx
 * @version 1.0
 * @date 2022年5月20日 10:14
 * @description: 重建二叉树
 */
class TreeNode{
 int val;
 TreeNode left;
 TreeNode right;
 TreeNode(int x){this.val = x;}
}


public class BuildTree {
 public static void main(String[] args) {
 int []preorder = {3,9,20,15,7};
 int []inorder = {9,3,15,20,7};
 TreeNode ans = new BuildTree_Solution().build(preorder,inorder);
 previsrt(ans);
 }
 public static void previsrt(TreeNode node){
 if(node == null){
 return;
 }
 System.out.println(node.val);
 previsrt(node.left);
 previsrt(node.right);
 }
}


class BuildTree_Solution{
 Map<Integer,Integer> map = new HashMap<Integer,Integer>();
 public TreeNode build(int[] preorder,int[] inorder){

 for(int i =0;i<inorder.length;i++){
 map.put(inorder[i],i);
 }
 //创建的树的根节点
 TreeNode root = mybuild(preorder,0,inorder.length-1,0);;
 return root;
 }

 //preorder_left : 前序遍历的左边界 preorder_right:前序遍历的右边界 inorder_left:中序遍历的左边界,inorder_left为了求左子树的个数
 public TreeNode mybuild(int[] preorder,int preorder_left,int preorder_right,int inorder_left){

 if(preorder_left > preorder_right){
 return null;
 }
 TreeNode root = new TreeNode(preorder[preorder_left]);
 int index = map.get(preorder[preorder_left]); //得到中序遍历中根节点的位置
 int left_size = index - inorder_left; //得到左子树的个数 也就拿到了左子树的范围

 //递归构造左子树 :给出左子树范围,构造左子树的时候 inorder_left不用变
 root.left = mybuild(preorder,preorder_left+1,preorder_left+left_size,inorder_left);
 //递归构造右子树 : 给出右子树的范围,构造右子树的时候 inorder_left是上一次中间节点(根节点)的+1,
 root.right = mybuild(preorder,preorder_left+left_size+1,preorder_right,index+1);
 return root;
 }
}