题解 | #重建二叉树#
重建二叉树
http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
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;
}
}