剑指 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;
    }
}

References

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