【剑指 offer】二叉搜索树的后序遍历序列

1、题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

如果是则返回true，否则返回false。

假设输入的数组的任意两个数字都互不相同。

样例:

输入：[4, 8, 6, 12, 16, 14, 10]
输出：true

2、问题描述：

• 判断一个二叉树是否是BST的后序遍历的结果。

3、问题关键：

• BST具有根结点比左孩子都大，比右孩子都小。
• 后序遍历：左 右 根。故把序列分成3部分，先左边全部小于根的结点，再判断结下的是否全部是大于根的，如果不是则返回false；
• BST的左右孩子也都是BST。递归遍历左右孩子。

4、C++代码：

class Solution {
public:
    vector<int> s;
    bool verifySequenceOfBST(vector<int> sequence) {
        s = sequence;
        return dfs(0, s.size() - 1);
    }
    bool dfs(int l , int r) {
        if (l >= r)  return true;//遍历完了所有结点都符合了。
        int k = l;
        int root = s[r];//当前序列的根结点。
        while(k < r && s[k] < root) k ++;//找到左子树。
        for (int i = k; i < r; i++) {
            if (s[i] < root) return false;//如果右子树有小于根的那么就不是 BST。
        }
        return dfs(l, k - 1) && dfs(k, r - 1);//递归遍历左右子树是否是BST。
    }
};