每天刷一道牛客题霸-第20天- 重建二叉树

题目

https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=190&&tqId=35426&rp=1&ru=/ta/job-code-high-rd&qru=/ta/job-code-high-rd/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 {
    public static TreeNode reConstructBinaryTree(int [] pre, int [] in) {
        HashMap<Integer,Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            inorderMap.put(in[i],i);
        }
        return buildTree(pre,inorderMap,0,pre.length-1,0);
    }
    public static TreeNode buildTree(int[] preorder, HashMap<Integer,Integer> inorderMap,int preStart,int preEnd, int inStart){
        if (preEnd < preStart){
            return null;
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        int rootStart = inorderMap.get(preorder[preStart]);
        int length = rootStart-inStart;
        root.left = buildTree(preorder,inorderMap,preStart+1,preStart+length,inStart);
        root.right = buildTree(preorder,inorderMap,preStart+length+1,preEnd,rootStart+1);
        return root;
    }
}