题解 | #重建二叉树#

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[] pre;
    HashMap<Integer, Integer> map = new HashMap<>();
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        this.pre = pre;
        for(int i = 0;i < vin.length;i++){
            map.put(vin[i],i);
        }
        return rec(0,0,vin.length-1);
    }
    public TreeNode rec(int root,int left, int right){
        if (left > right){
            return null;
        }
        TreeNode node = new TreeNode(pre[root]);
        int i = map.get(pre[root]);
        node.left = rec(root+1, left, i-1);
        node.right = rec(root+i-left+1,i+1, right);
        return node;
    }
}