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

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

     5
    / \
   2   6
  / \
 1   3
示例 1：

输入: [1,6,3,2,5]
输出: false
示例 2：

输入: [1,3,2,6,5]
输出: true
 

提示：
数组长度 <= 1000

思路

因为为后续遍历，所以一定满足，最后的节点一定是根节点，所以我们找到了根节点，然后因为这个树为二叉搜索树，所以根节点的左边的值一定小于根节点，右边的值一定大于根节点，所以我们在前面的数组中一定能找到left和right，如果这个数组不满足这个条件那么就一定不能构建成搜索树。

这样我们找到了left和right后依次类推，我们逐个判断left和right是不是二叉搜索树。

和剑指offer第七题类似，也是通过指针和前序中序后序遍历确定根节点

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private static class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    private boolean recur(int[] postorder, int i, int j) {
        if (i >= j) {
            return true;
        }
        int p = i;
        // 要找到比本节点小的最后的那个值
        while (postorder[p] < postorder[j]) {
            p++;
        }
        int mid = p;
        // 要找到比本节点大的最后的那个值
        while (postorder[p] > postorder[j]) {
            p++;
        }
        // 这里要确保找到的mid左边的数一定比根节点（postorder[j]）小，mid右边的数一定要比根节点大
        return p == j && recur(postorder, i, mid - 1) && recur(postorder, mid, j - 1);
    }

}