题解 | #重建二叉树#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

/**
 * NC12 重建二叉树
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 程序入口
     *
     * 递归: 前序遍历
     *
     * @param preOrder int整型一维数组
     * @param vinOrder int整型一维数组
     * @return TreeNode类
     */
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        int num = preOrder.length;
        if(num == 0){
            return null;
        }
        // 当前根结点
        int rootVal = preOrder[0];
        TreeNode root = new TreeNode(rootVal);
        // 当前根结点 左子树节点个数
        int left = 0;
        while(vinOrder[left] != rootVal){
            left++;
        }
        if(left > 0){
            // int[] pre = new int[left];
            // int[] vin = new int[left];
            // System.arraycopy(preOrder, 1, pre, 0, left);
            // System.arraycopy(vinOrder, 0, vin, 0, left);
            // root.left = reConstructBinaryTree(pre, vin);

            root.left = reConstructBinaryTree(Arrays.copyOfRange(preOrder, 1, left+1), Arrays.copyOfRange(vinOrder, 0, left));
        }
        // 当前根结点 右子树节点个数
        int right = num-(left+1);
        if(right > 0){
            // int[] pre = new int[right];
            // int[] vin = new int[right];
            // System.arraycopy(preOrder, left+1, pre, 0, right);
            // System.arraycopy(vinOrder, left+1, vin, 0, right);
            // root.right = reConstructBinaryTree(pre, vin);

            root.right = reConstructBinaryTree(Arrays.copyOfRange(preOrder, left+1, num), Arrays.copyOfRange(vinOrder, left+1, num));
        }

        return root;
    }
}