题解 | #二叉搜索树的后序遍历序列#

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

http://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd

class Solution {
public:
    //由给定数组判断是不是二叉搜索树的后序遍历可以这样做
    //首先最后一个值肯定是树的根节点,根据这个值的大小把前面的数组分为左子树部分和右子树部分
    //然后左子树的所有值必须小于这个值,右子树的所有值必须大于这个值,如果出现反例则直接返回false
    bool f(vector<int> sequence,int start, int end){
        if(start>=end){//子树为空树或者只有一个节点的子树直接返回true
            return true;
        }
        int root=sequence[end];//取最后一个值
        //根据这个值的大小把数组分成左子树数组和右子树数组
        int i=start;
        for(i=start;i<end;i++){
            if(sequence[i]>root){//说明从i开始往后的数组部分是属于右子树数组部分
                break;
            }
        }
        //然后根据分出来的左右子树数组来判断是否满足二叉搜索树的特点
        //这里有个优化细节,不用判断左子树数组了,因为左子树数组一定满足,只需要判断右子树数组即可
        for(int index=i+1;index<end;index++){
            if(sequence[index]<=root){//右子树数组应该全部大于root才对,此时直接返回false
                return false;
            }
        }
        return f(sequence, start,i-1)&&f(sequence, i, end-1);
    }
    
    bool VerifySquenceOfBST(vector<int> sequence) {

        
        if(sequence.size()==0){//空树约定不是二叉搜索树
            return false;
            
        }
        if(sequence.size()==1){//只有一个节点的二叉树一定是二叉搜索树
            return true;
        }
        
        return f(sequence, 0, sequence.size()-1);
        
        
    }
};
全部评论

相关推荐

Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-10 12:05
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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