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

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

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

题目

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

方法一(最开始自己写的):

思路

先确定根节点,即root
然后遍历一遍数据,看看是否符合要求
1、左子树均小于根节点
2、右子树均大于根节点
但是这边会有特殊情况(一开始没想到更简单的。只能通过自己设定判断条件flag和pos。):只有左子树和只有右子树

代码

function VerifySquenceOfBST1(sequence)
{
    if(sequence.length==0)
        return false;
    return check(sequence)
}

function check(sequence){
    if(sequence.length<=1){
        return true;
    }
    var root=sequence[sequence.length-1];//后序遍历最后一个为根节点
    var pos=-1,i,flag=false;
    for(i=0;i<sequence.length-1;i++){
        if(sequence[i]<root&&!flag){
            pos=i;
        }
        else if(sequence[i]>root&&!flag){//转择点,当前i大于root,i-1小于root
            if(pos==-1){//不存在左子树的情况
                flag=true;
                pos=-2;
            }
            else{//左子树存在,即将进入右子树
                flag=true;//只能一次有效
            }
        }
        else if(flag&&sequence[i]<root){//此处表示已遍历完左子树,开始右子树比较
            flag=false;
            pos=-3;
            break;
        }
    }
    // console.log(flag,pos)
    if(!flag&&pos<=-2){
        return false;
    }
    else{
        // console.log(sequence.slice(0,pos+1),sequence.slice(pos+1,sequence.length-1))
        return check(sequence.slice(0,pos+1))&&check(sequence.slice(pos+1,sequence.length-1))
    }
}

方法二(参考别人优化)

思路

后序遍历的最后一个为根节点,且如果是正确的序列,则序列最后一个数值会将该序列的划分成两块,即左子树和右子树。然后递归实现。

代码

function VerifySquenceOfBST(sequence){
    if(!sequence.length)
        return false;
    return Judge(sequence,0,sequence.length-1);
}
function Judge(sequence,start,end){
    if(start>end){
        return true;
    }
    var i=end-1;
    while(i>=start&&sequence[i]>sequence[end]){  //找到左右子树临界点
        i--;
    }
    for(var j=i-1;j>=start;j--){//遍历查看左子树是否符合预期,即所有左子树小于根节点
        if(sequence[j]>sequence[end]){
            return false;
        }
    }
    return Judge(sequence,start,i)&&Judge(sequence,i+1,end-1);
}
全部评论

相关推荐

机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 14:35
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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