public static Node process3(int[] posArr, int L, int R) {
if (L > R) {
return null;
}
// L<=R
// [L...R] [R]为头结点
Node head = new Node(posArr[R]);
if (L == R) {
return head;
}
int M = -1;
// L<R
// [L..R-1]
for (int i = L; i < R; i++) {
if (posArr[i] < posArr[R]) {
M = i;
}
}
if (M == -1) {
//只有右树
head.right = process3(posArr, L, R - 1);
} else if (M == R - 1) {
//只有左树
head.left = process3(posArr, L, R - 1);
} else {
//[L..M]构建左树 [M+1..R-1]构建右树
head.left = process3(posArr, L, M);
head.right = process3(posArr, M + 1, R - 1);
}
return head;
}
