题解 | #重建二叉树#

import java.util.*;

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {

        if(pre.length == 0){
            return null;
        }
        if (pre.length == 1){
            return new TreeNode(pre[0]);
        }
        if (pre.length == 2){
            TreeNode root = new TreeNode(pre[0]);
            TreeNode child = new TreeNode(pre[1]);
            if (pre[0] == vin[0]){
                root.right = child;
            }else {
                root.left = child;
            }
            return root;
        }

        ArrayList<Integer> left = new ArrayList<>();
        ArrayList<Integer> right = new ArrayList<>();

        boolean isLeft = true;
        for (int i : vin) {
            if (i==pre[0]){
                isLeft = false;
                continue;
            }
            if (isLeft){
                left.add(i);
            }else {
                right.add(i);
            }
        }
        int[] preLeft = new int[left.size()];
        int[] preRight = new int[right.size()];
        for (int i = 0; i < preLeft.length; i++) {
            preLeft[i] = pre[i+1];
        }
        for (int i = 0; i < preRight.length; i++) {
            preRight[i] = pre[i+1+preLeft.length];
        }

        int[] vinLeft = new int[left.size()];
        int[] vinRight = new int[right.size()];

        for (int i = 0; i < left.size(); i++) {
            vinLeft[i] = left.get(i);
        }

        for (int i = 0; i < right.size(); i++) {
            vinRight[i] = right.get(i);
        }

        TreeNode leftNode = preLeft.length==0?null: reConstructBinaryTree(preLeft,vinLeft);
        TreeNode rightNode = preRight.length==0?null:reConstructBinaryTree(preRight,vinRight);

        TreeNode rootNode = new TreeNode(pre[0]);
        rootNode.left = leftNode;
        rootNode.right = rightNode;
        return rootNode;
    }


}

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }