题解 | #重建二叉树#

记录下菜鸡写的比较详细的写法

public class JZ4_重建二叉树 {
    public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre.length == 0 || in.length == 0) return null;
        //前序数组的第一个值即接下来的树的头节点
        TreeNode root = new TreeNode(pre[0]);

        //找到前序的根在中序的位置
        int rootPos = -1;
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                rootPos = i;
                break;
            }
        }
        //构建下一次递归的数组
        int[] nextPreLeft = Arrays.copyOfRange(pre, 1, rootPos + 1);
        int[] nextInLeft = Arrays.copyOfRange(in, 0, rootPos);
        int[] nextPreRight = Arrays.copyOfRange(pre, rootPos + 1, pre.length);
        int[] nextInRight = Arrays.copyOfRange(in, rootPos + 1, pre.length);

        root.left = reConstructBinaryTree(nextPreLeft, nextInLeft);
        root.right = reConstructBinaryTree(nextPreRight, nextInRight);

        return root;
    }
}