题解 | #重建二叉树#

import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
//总体思路：递归
//pre为前序遍历数组，其第一个元素为树的根节点
//前序和中序的共同特点是，都是左子树在左，右子树在右
//根据树的根节点在vin中序中的位置，将数组分为左和右两个子树，进而递归
//时间复杂度：主要考虑查找耗时，O(NlogN)-O(N^2)，最优为N/2+2*N/4+...=N/2*logN，最差为N+(N-1)+(N-2)+...=N^2/2
//空间复杂度：主要是数组复制的空间，(N-1)+(N-2)+...=N^2/2, O(n^2)
	//这里的find函数用于查找数组中指定元素的索引。不能用Arrays.binarySearch，那个需要先排序
    public int find(int[] array, int value) {
        for(int i=0; i<array.length; i++)
            if(array[i] == value)
                return i;
            return -1;
    }
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
    	//打印数组要先转换成string，不然打印的是地址
        System.out.print(Arrays.toString(pre));
        System.out.print(Arrays.toString(vin));
        int lo = 0;
        int hi = vin.length;
		//如果为空，也是一个递归到底的条件，返回空即可
        if(pre != null && pre.length != 0){
            TreeNode rootnode = new TreeNode(pre[0]);
            //递归到底条件：数组长度为1
            if(vin.length == 1){
                return rootnode;
            }
            System.out.print(Arrays.toString(pre));
            System.out.print(Arrays.toString(vin));
            //找到根节点在中序遍历数组中的索引
            int mid = find(vin, pre[0]);
            System.out.print(mid);
            //边界条件：左子树或者右子树为空
            if(mid != 0){
                int[] left_vin = Arrays.copyOfRange(vin, lo, mid);
                int[] left_pre = Arrays.copyOfRange(pre, 1, left_vin.length+1);
//                System.out.print(Arrays.toString(left_vin));
                rootnode.left = reConstructBinaryTree(left_pre, left_vin);
                System.out.print("left suc");
            }
            if(mid != pre.length){
                int[] right_vin = Arrays.copyOfRange(vin, mid+1, hi);
                int[] right_pre = Arrays.copyOfRange(pre, pre.length-right_vin.length, pre.length);
//                System.out.print(Arrays.toString(right_vin));
                rootnode.right = reConstructBinaryTree(right_pre, right_vin);
                System.out.print("right suc");
            }
            return rootnode;
        }
        return null;
    }
}