JZ23 二叉搜索树的后序遍历序列*

题目描述

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

思路

首先,要知道什么是二叉搜索树:对于任何一棵子树来说,根节点都比它的左子树大,比它的右子树小
二叉搜索树有什么特点呢?
下面是一棵二叉搜索树:

            10
           /  \
          8   13
         / \  / \
        7  9 11 17

前序遍历:10,8,7,9,13,11,17;
第一个是根节点,后面分别为它的左右子树(左都比它小,右都比它大)
中序:7,8,9,10,11,13,17;
中序遍历单调递增
后序遍历:7,9,8,11,17,13,10
最后一个节点是根节点,前面分别为它的左子树和右子树(左都比它小,右都比它大)

用递归的思想
关键点:
(1)找这个序列中左右子树的分界点
(2)递归分别判断左右子树

我的错误:
未考虑特殊情况(没有左子树或者没有右子树的情况)
一开始我的bound没有给初始值,所以出错了,不能只想着最一般的情况!!!

代码

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size()<=0)
            return false;
        int left=0;
        int right=sequence.size()-1;
        return Verify(sequence,left,right);
    }

    bool Verify(vector<int> sequence,int left,int right)
    {
        if(left>=right)
            return true;
        int root=sequence[right];
        int flag=0;  //标志出现了比根节点大的数,0表示没有出现,1表示出现了
        int bound=0;  //定义小于和大于之间的边界
        for(int i=left;i<right;i++)
        {
            if(sequence[i]>root && flag==0)
            {
                bound=i;
                flag=1;   //出现之后flag变为1
            }
            else if(sequence[i]<root && flag==1)
                {
                    return false;       //如果在flag=1(已经有比根节点大了数了还出现了比根节点小的,那就返回false)
                }
        }
        return Verify(sequence,left,bound-1)&& Verify(sequence,bound,right-1);

    }
};
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务