已知BST的前序遍历,还原BST
public static TreeNode getRoot(int[] arr, List<Integer> list){
int index = -1;
for (int i = 0; i < arr.length; i++) {
if (list.contains(arr[i])){
index = Collections.binarySearch(list, arr[i]);// 以根节点进行分割
break;
}
}
TreeNode treeNode = new TreeNode(list.get(index));
List<Integer> left = list.subList(0, index);
if (left.size() > 0){
treeNode.left = getRoot(arr, left);
}
List<Integer> right = list.subList(index + 1, list.size());
if (right.size() > 0){
treeNode.right = getRoot(arr, right);
}
return treeNode;
}