题解 | #重建二叉树#

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    Map<Integer,Integer> m = new HashMap<>();
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if(pre == null || pre.length == 0) return null;
        for(int i = 0; i < vin.length; i++){
            m.put(vin[i], i);
        }
       return  BuildTree(pre, vin, 0, pre.length - 1, 0, vin.length - 1);
    }
    public TreeNode BuildTree(int [] pre, int [] vin, int pStart, int pEnd, int inStart, int inEnd){
        if(pStart > pEnd || inStart > inEnd) return null;
        int rootVal = pre[pStart];
        int rootInIndex = m.get(rootVal);
        int leftSize = rootInIndex - inStart;
        TreeNode root = new TreeNode(rootVal);
        root.left = BuildTree(pre, vin, pStart + 1, pStart + leftSize, inStart, rootInIndex - 1);
        root.right = BuildTree(pre, vin, pStart + leftSize + 1, pEnd, rootInIndex + 1, inEnd);
        return root;
    }
}