题解 | #重建二叉树#

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 (vinOrder.length == 0)
            return null;

        int preIndex = 0 ;
        int vinIndex = 0 ;
	  //中序数组中最先在前序数组中出现的是根节点
        while (preOrder[preIndex] != vinOrder[vinIndex]) {
            
            if (vinIndex == (vinOrder.length - 1)) {
                preIndex++;
                vinIndex = 0;
            }else{
                vinIndex++;
            }
            
        }

        TreeNode root = new TreeNode(preOrder[preIndex]);
        int[] left ;
        int[] right;
        if(vinIndex==0)
            left = new int[0];
        else    
            left = Arrays.copyOfRange(vinOrder, 0, vinIndex);
        if(vinIndex==vinOrder.length-1)
            right = new int[0];
        else
            right = Arrays.copyOfRange(vinOrder, vinIndex + 1, vinOrder.length);
        
        root.left = reConstructBinaryTree(preOrder, left);
        root.right = reConstructBinaryTree(preOrder, right);

        return root;
    }
}