Poison

剑指 Offer 33. 二叉搜索树的后序遍历序列

Recursion
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
class Solution {
public boolean verifyPostorder(int[] postorder) {
// left, right, root

if (postorder.length <= 1) {
return true;
}

return verifyPostorder(postorder, 0, postorder.length - 1);
}

private boolean verifyPostorder(int[] postorder, int i, int j) {
if (i >= j) {
return true;
}

int root = postorder[j];
for (int k = i; k < j; k++) {
// find right tree startIndex
if (postorder[k] > root) {
for (int l = k + 1; l < j; l++) {
if (postorder[l] < root) {
return false;
}
}
return verifyPostorder(postorder, i, k - 1) && verifyPostorder(postorder, k, j - 1);
}
}

return verifyPostorder(postorder, i, j - 1);
}
}
Recursion
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
class Solution {
public boolean verifyPostorder(int[] postorder) {
// postorder: left, right, root

return verifyPostorder(postorder, 0, postorder.length - 1);
}

private boolean verifyPostorder(int[] postorder, int startIndex, int endIndex) {
if (startIndex >= endIndex) {
return true;
}

int rootValue = postorder[endIndex];
int i = startIndex;
while (postorder[i] < rootValue) {
i++;
}

// 此时 i 指向右子树(如果存在)的节点
int rightTreeStartIndex = i;
while (postorder[i] > rootValue) {
i++;
}

// 只有 i 指向 endIndex 才能够划分左右子树
return i == endIndex && verifyPostorder(postorder, startIndex, rightTreeStartIndex - 1) && verifyPostorder(postorder, rightTreeStartIndex, endIndex - 1);
}
}
Stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public boolean verifyPostorder(int[] postorder) {
Stack<Integer> increaseStack = new Stack<>();
int root = Integer.MAX_VALUE;

for (int i = postorder.length - 1; i >= 0; i--) {
if (postorder[i] > root) {
return false;
}
while (!increaseStack.isEmpty() && postorder[i] < increaseStack.peek()) {
root = increaseStack.pop();
}
increaseStack.push(postorder[i]);
}

return true;
}
}
Reference

剑指 Offer 33. 二叉搜索树的后序遍历序列