-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBstFromPreorder.java
More file actions
66 lines (61 loc) · 2.11 KB
/
BstFromPreorder.java
File metadata and controls
66 lines (61 loc) · 2.11 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package basic.tree;
import java.util.Arrays;
/**leetcode 1008
* 根据先序遍历重建二叉搜索树
* @author JunjunYang
* @date 2020/1/1 20:49
*/
public class BstFromPreorder {
int index;
public static void main(String[] args) {
TreeNode treeNode=new BstFromPreorder().solution(new int[]{5,3,2,4,7,6,8});
System.out.println(Arrays.toString(TraverseOrder.preOrderRecursion(treeNode).toArray()));
}
public TreeNode solution(int[] preOrder) {
index=0;
return solution(preOrder,Integer.MIN_VALUE,Integer.MAX_VALUE);
}
/**
* 设定最大值与最小值，以设置终止条件
* 巧妙的通过最大最小值来终止递归
* @param preOrder
* @param minValue
* @param maxValue
* @return
*/
private TreeNode solution(int[] preOrder,int minValue,int maxValue) {
//查找到数组末尾，返回null
if(index==preOrder.length) {
return null;
}
int val=preOrder[index];
//遍历到的value已经不符合二叉搜索树的定义，返回null
if(val<minValue || val>maxValue) {
return null;
}
index++;
TreeNode root=new TreeNode(val);
root.left=solution(preOrder,minValue,val);
root.right=solution(preOrder,val,maxValue);
return root;
}
/**
* 解法2，分别找到左子区间和右子区间，递归
* @param preorder
* @return
*/
public TreeNode bstFromPreOrder(int[] preOrder) {
return bstFromPreOrder(preOrder,0,preOrder.length);
}
//左闭右开区间
public TreeNode bstFromPreOrder(int[] preOrder, int start, int end) {
if(start >= end) return null;
int i=start+1;
//找到第一个大于根节点的下标，也就是右子树的起点
for(;i<end && preOrder[i]<preOrder[start];i++);
TreeNode root = new TreeNode(preOrder[start]);
root.left = bstFromPreOrder(preOrder,start+1,i);
root.right = bstFromPreOrder(preOrder,i,end);
return root;
}
}