题解 | #重建二叉树#

import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
            //递归重建
            //先序遍历的第一个,肯定是根节点,
            //现需遍历的第二个,肯定是左节点的第一个根节点
            return reConstructBinaryTreeLeft(pre,vin);
    }
    //构建左子树
    public TreeNode reConstructBinaryTreeLeft(int [] pre,int [] vin){
         TreeNode root;
        //创建本级节点
        if(pre.length>0){
            root = new TreeNode(pre[0]);
        }else{
            root = null;
            return root;
        }
        //把先序和中序拆分开来
        int[] preLeft = new int[10] ;
        int[] vinLeft = new int[10] ;

        int[] preRight = new int[10] ;
        int[] vinRight = new int[10] ;
        boolean flag = false;
        int index = 0;
        for(int i = 0,j = 0;i<vin.length;i++,j++){
            if(flag){
                preRight[j]  = pre[i];
                vinRight[j]  = vin[i];
            }
            if(pre[0] == vin[i]){
                preLeft = new int[i];
                vinLeft = new int[i];
                preRight = new int[vin.length - i-1];
                vinRight = new int[vin.length - i-1];
                j = -1;
                index = i ;
                flag =true;
            }
        }
        for(int i = 0;i<index;i++){
            preLeft[i] = pre[i+1];
            vinLeft[i] = vin[i];
        }
        //判断是左子节点还是右子节点
        root.left = reConstructBinaryTreeLeft(preLeft,vinLeft);
        root.right = reConstructBinaryTreeLeft(preRight,vinRight);

        return root;
    }
    
}