剑指offer-23-二叉搜索树的后序遍历

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

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

思路

了解二叉树和后序遍历的特点就会做了
利用根结点分割左右子树,左<根<右

代码

import java.util.*;
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        //二叉树搜索树是左<根<右
        //后序遍历是 左右根,在数组中,根结点是最后一个
        //前序遍历  根左右,在数组种,根结点是第一个
        //中序结点 左根右,在数组种,特点是根结点可以划分左右子树
         if(sequence.length<=0){return false;}
        return just(sequence);
    }

    public boolean just(int[] sequence){
        if(sequence.length<=2){
            return true;
        }
        int root=sequence[sequence.length-1];
        int p=0;
        while(p<sequence.length&& sequence[p]<root){
            p++;
        }
        for(int i=p;i<sequence.length-1;i++){
            if(sequence[i]<root){
                return false;
            }
        }
        return just(Arrays.copyOfRange(sequence,0,p)) &&
            just(Arrays.copyOfRange(sequence,p,sequence.length-1));
    }
}
剑指offer与数据结构 文章被收录于专栏

本专栏包括剑指offer题目和一些刷题用的数据结构,单调栈,树状数组,差分数组,后面还会更新红黑树等较为复杂的数据结构

全部评论

相关推荐

05-26 10:24
门头沟学院 Java
qq乃乃好喝到咩噗茶:其实是对的,线上面试容易被人当野怪刷了
点赞 评论 收藏
分享
被加薪的哈里很优秀:应该继续招人,不会给你留岗位的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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