题解 | #重建二叉树#

import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
//1.从头遍历pre
//2.找到vin上对应的元素
//3.如果为空，就为空，否则构建节点
//4.将自己的元素构建节点
//5.将左边元素传入左边建树
//6.将右边元素传入右边建树

public class Solution {

    // TreeNode root = null;
    public TreeNode reConstructBinaryTree(int[] pre,int[] vin){
        if(pre.length == 0 ){
            return null;
        }
        TreeNode node = new TreeNode(pre[0]);
        int k ;

        for(k = 0;k<vin.length;k++){
            if(pre[0]==vin[k]){
                break;
            }
        }
        int[] left = Arrays.copyOfRange(vin,0,k);
        int[] right = Arrays.copyOfRange(vin,k+1,vin.length);
        if(left.length>0){
            int[] pre_left = Arrays.copyOfRange(pre,1,left.length+1);
            node.left = reConstructBinaryTree(pre_left,left);
        }
        if(right.length>0){
            int[] pre_right = Arrays.copyOfRange(pre,left.length+1,vin.length);
            node.right = reConstructBinaryTree(pre_right,right);
        }    
        return node;
    }
}

//     public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
//         if(pre.length == 0 ){
//             return null;
//         }
//         TreeNode node = new TreeNode(pre[0]);
//         int k ;

//         for(k = 0;k<vin.length;k++){
//             if(pre[0]==vin[k]){
//                 break;
//             }
//         }
//         int[] left = Arrays.copyOfRange(vin,0,k);
//         int[] right = Arrays.copyOfRange(vin,k,vin.length);
//         if(left.length>0){
//             int[] pre_left = Arrays.copyOfRange(pre,1,left.length+1);
//             node.left = construct(pre_left,left);
//         }
//         if(right.length>0){
//             int[] pre_right = Arrays.copyOfRange(pre,left.length+1,vin.length);
//             node.right = construct(pre_right,right);
//         }    
    

//         return node; 
//     }
// }