刷题笔记（1） 一个序列是否为二叉搜索树的遍历结果

1.输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

二叉搜索树：具体定义：https://blog.csdn.net/zj1131190425/article/details/88654541

是一棵二叉树，可能为空，非空的二叉搜索树满足以下特征：

1.每个元素都有唯一的关键字

2.根节点的左子树中，元素的关键字都小于根节点的关键字

3.根节点的右子树中，元素的关键字都大于根节点的关键字

4.根节点左右子树也都是二叉搜索树

根据二叉搜索树的定义来做：

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) 
    {
        int size = sequence.size();
        if(size==0)
            return false;
        vector<int> left;    // 左子树
        vector<int> right;    // 右子树
        int root = sequence[size-1];   // 根节点
        int i;    // 寻找左右子树的分界点
        for(i=0; i<size-1; i++)
        {
            if(sequence[i]>root)
            {
                break;   // 找到左右分解
            }
        }

        for(int j=i; j<size-1; j++)
        {
            if(sequence[j]<root)
                return false;
        }

        if(i!=0)  // 有左子树
        {
            for(int j=0; j<i; j++)
            {
                left.push_back(sequence[j]);
            }
        }

        if(i!=size-1-1)  // 有右子树
        {
            for(int j=i; j<size-1; j++)
            {
                right.push_back(sequence[j]);
            }
        }

        if(left.size()>1)
            VerifySquenceOfBST(left);
        if(right.size()>1)
            VerifySquenceOfBST(right);
        return true;
    }
};

这道题目利用递归的方法解题：

链接：https://www.nowcoder.com/questionTerminal/a861533d45854474ac791d90e447bafd
来源：牛客网

1、确定root；

2、遍历序列（除去root结点），找到第一个大于root的位置，则该位置左边为左子树，右边为右子树；

3、遍历右子树，若发现有小于root的值，则直接返回false；

4、分别判断左子树和右子树是否仍是二叉搜索树（即递归步骤1、2、3）。