牛客题霸NC12重建二叉树Java题解

牛客题霸NC12重建二叉树Java题解
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=117&&tqId=35043&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
方法：递归
解题思路：在前序遍历中找根节点，可将中序遍历划分为左、根、右。根据中序遍历中的左、右子树的节点数量，可以将前序遍历划分为根、左、右。

import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

    int[] po;
    HashMap<Integer,Integer> map = new HashMap<>();

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        po = pre;
        for(int i=0;i<in.length;i++){
            map.put(in[i],i);
        }
        return recur(0,0,in.length-1);
    }

     private TreeNode recur(int pre_root,int in_left,int in_right){

        if(in_left>in_right){
            return null;
        }

        TreeNode root = new TreeNode(po[pre_root]);  // 建立根节点

        //获取根节点在中序中的索引
        int i = map.get(po[pre_root]); 

        root.left = recur(pre_root+1,in_left,i-1);  //中序
        root.right = recur(pre_root+(i-in_left)+1,i+1,in_right); //中序

        return root;  
    }
}