一、题目描述

JZ23 二叉搜索树的后序遍历序列
题目大意：输入一个序列, 判断它是不是某二叉搜索树的后序遍历结果
注意审题：假设输入序列的任意两个数字都互不相同且空树不是二叉搜索树

二、算法1（分治）

解题思路

  1. 二叉树的后序遍历顺序是：左子树 -> 右子树 -> 根节点
  2. 因此序列的最后一个数代表了根节点
  3. 因此我们可以将一个序列划分为3段, 左子树+右子树+根, 例如[4, 8, 6, 12, 16, 14, 10]可以根据根节点的值将其划分为左子树[4, 8, 6], 右子树[12, 16, 14], 根[10], 由于我们是先确定的右子树区间, 因此当左子树区间中出现大于根节点的值时, 序列不合法, 我们再采用分治的思想, 对于每段序列代表的子树, 检查它的左子树和右子树, 当且仅当左右子树都合法时返回true
    图片说明

代码实现（C++11）

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int n = sequence.size();
        if(n == 0) return false;    // 注意审题, 约定空树不是二叉搜索树
        return check(sequence, 0, n - 1);
    }

    bool check(vector<int>& sequence, int l, int r){
        if(l >= r) return true;    // 若当前子树只有一个节点

        int root = sequence[r];    // 当前子树的根节点

        // 划分出右子树
        int j = r - 1;
        while(j >= 0 && sequence[j] > root) j--;

        // 检查左子树是不是存在大于根节点的数
        for(int i = l; i <= j; i++){
            if(sequence[i] > root) return false;
        }

        // 分治法检查左子树和右子树
        return check(sequence, l, j) && check(sequence, j + 1, r - 1);
    }
};

时间复杂度：O(n^2), n为二叉树节点的个数, 当树为链式时时间复杂度最坏为O(n^2)
空间复杂度：O(n), 当树为链式结构时, 递归深度为n

三、算法2（栈）

解题思路

  1. 实际上二叉树的中序遍历和后序遍历对应着一种栈的压入、弹出序列, 而对后序遍历序列从小到大排序就得到了中序遍历序列
  2. 我们得到中序遍历序列后, 将其作为入栈序列, 检查后序遍历序列是不是一个合法的出栈序列即可
  3. 对于检查栈的合法压入、弹出序列问题, 请看栈的压入、弹出序列题解

代码实现（C++11）

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty()) return false;
        vector<int> inorder(sequence);
        sort(inorder.begin(), inorder.end());
        return IsPopOrder(inorder, sequence);
    }

    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
         int n = pushV.size();
         stack<int> stk;    // 使用STL中的栈容器
         int i = 0, j = 0;
         while(i < n){
             stk.push(pushV[i]);    // 首先将pushV[i]入栈
             while(!stk.empty() && stk.top() == popV[j]){    // 不断检查栈顶
                 ++j;
                 stk.pop();
             }
             ++i;
         }
         return j == n;    // 判断能否成功对应
     }
};

时间复杂度：O(nlogn), 时间复杂度取决于排序
空间复杂度：O(n), 额外数组和辅助栈的空间