题解 | #重建二叉树#

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param preOrder int整型一维数组 
     * @param vinOrder int整型一维数组 
     * @return TreeNode类
     */
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        // write code here
        if(preOrder.length==0){
            return null;
        }
        
        
        return getResult(preOrder,vinOrder);
    }

    private TreeNode getResult(int[] preOrder, int[] vinOrder) {
        // TODO
        if(preOrder.length==0){
            return null;
        }
        TreeNode root = new TreeNode(preOrder[0]);
        int middle = root.val;
        int length_left = 0;
        int length_right = 0;
        boolean mid = false;
        for(int i = 0; i < vinOrder.length; length_left++, i++){
            if(vinOrder[i] == root.val){
                mid = true;
                break;
            }
        }
        length_right = vinOrder.length-1-length_left;
        int preleft[] = new int[length_left];
        int vinleft[] = new int[length_left];
        int preright[] = new int[length_right];
        int vinright[] = new int[length_right];
        for(int i = 0; i < length_left; i++){
            preleft[i] = preOrder[i+1];
            vinleft[i] = vinOrder[i];
        }
        for(int i = 0; i < length_right; i++){
            preright[i] = preOrder[length_left+i+1];
            vinright[i] = vinOrder[length_left+i+1];
        }
        root.left = getResult(preleft,vinleft);
        root.right = getResult(preright,vinright);
        return root;

    }
}