题解 | #重建二叉树#

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class Solution {
    //pre，vin为root根节点的二叉树，前序和中序数组
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if(pre.length==0 || pre == null){
            return null;
        }
        int index = findIndex(pre,vin);
        TreeNode root = new TreeNode(pre[0]);
        //递归,寻找以root的左子结点作为
        root.left = reConstructBinaryTree(returnChild(pre,1,index+1),returnChild(vin,0,index));
        root.right =  reConstructBinaryTree(returnChild(pre,index+1,pre.length),returnChild(vin,index+1,vin.length));   
        return root;    
    }
    public int[] returnChild(int[] target,int start,int end){
        int[] newChar = new int[end - start];
        for(int i = start; i < end;i++){
            newChar[i-start] = target[i];
        }
        return newChar;
    }
    //找一个index，index为根节点
    public int findIndex(int[] pre,int[] vin){
        for(int i = 0; i < vin.length;i++){
            if(pre[0] == vin[i]){
                return i;
            }
        }
        return 0;
    }
}