二叉搜索树（BST）又称二叉查找树或二叉排序树。若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索
问题：已知一个搜索二叉树，后序遍历的数组posArr，请根据posArr,重建出整棵数，返回新建树的头节点
例如 数组posArr= [2,4,3,6,7,8,5],建出二叉树：
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
| public class PosArrayToBST {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int v){
value = v;
}
}
public static Node startPosArrayToBST(int[] posArr){
return process(posArr, 0, posArr.length-1);
}
public static Node process(int[] posArr, int L, int R){
if (L>R){
return null;
}
Node head = new Node(posArr[R]);
if (L == R){
return head;
}
int M = L -1;
int left = L;
int right = R;
while (left <= right){
int mid = left + ((right - left) >> 1);
if (posArr[mid] < posArr[R]){
M = mid;
left = mid +1;
}else {
right = mid - 1;
}
}
head.left = process(posArr, L, M);
head.right = process(posArr, M+1, R-1);
return head;
}
}
|
M = L -1 原因：当二叉树既有左子树，又有右子树，M会改变，初始值无所谓，但当二叉树只有左边时（[1,2,3,4,5]），M最后的结果就为R-1，后续的递归
1
2
3
| head.right = process(posArr, M+1, R-1);
head.right = process(posArr, R, R-1);
|
右边同理。等同于
1
2
3
4
5
6
7
8
| if(M == -1){
head.right = process(posArr, L, R-1);
}else if(M == R-1){
head.left = process(posArr, L, R-1);
}else{
head.left = process(posArr, L, M);
head.right = process(posArr, M+1, R-1);
}
|
以上算法，最坏情况下时间复杂度 O(N * ㏒₂N)
问题二：给定长度为m的字符串aim,以及一个长度为n的字符串str。问能否在str中找到一个长度为m的连续子串，使得这个子串刚好由aim的m个字符组成，顺序无所谓，返回任意满足条件的一个子串的起始位置，未找到返回-1。
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
67
| public class containExactly {
public static int wayOne(String s, String a){
if(s == null || a == null || s.length() < a.length()){
return -1;
}
char[] aim = a.toCharArray();
System.out.println("aim 的值为" + aim);
Arrays.sort(aim);
String aimSort = String.valueOf(aim);
for(int L = 0; L< s.length(); L++){
for(int R = L; R < s.length(); R++){
char[] cur = s.substring(L, R+1).toCharArray();
Arrays.sort(cur);
System.out.println(cur);
String curSort = String.valueOf(cur);
if (curSort.equals(aimSort)){
return L;
}
}
}
return -1;
}
public static int wayTwo(String s, String a){
if(s == null || a == null || s.length() < a.length()){
return -1;
}
char[] aim = a.toCharArray();
int[] count = new int[256];
int M = aim.length;
char[] str = s.toCharArray();
for (int i = 0; i < M; i++) {
count[aim[i]] ++;
}
int inValidTimes = 0, R = 0;
for (; R< M; R++){
if(count[str[R]]-- <=0){
inValidTimes++;
}
}
System.out.println(inValidTimes);
for(; R < str.length; R++){
if (inValidTimes == 0){
return R-M;
}
if (count[str[R]]-- <= 0){
inValidTimes++;
}
if (count[str[R - M]]++ < 0){
inValidTimes--;
}
}
return inValidTimes == 0 ? R - M : -1;
}
public static void main(String[] args) {
String string = "abcdabcdsfcas";
String a = "abc";
int result = wayTwo(string, a);
System.out.println(result);
}
}
|
方法二解释：假设 aim = “acabb”, str = “caabcb”, M为aim的长度，值为5，count 记录aim每一个字符出现的次数，即第一个for循环。第二个for循环， str 前 M个字符在count列表出现的次数，刚好减掉aim在count列表里次数的值，则说明str前M个字符符合要求，如果不符合则进入第三个for循环，判断str中[1…M]的字符是否满足要求，否则再次进入第三个for循环，判断str中的[2….M+1]字符是否满足要求。
