变强日记9

主要内容

概括的解释下线程的几种可用状态
算法：判断一个序列是不是二叉查找树的后序遍历

概括的解释下线程的几种可用状态

线程有五个状态，它们分别是：

新建：新创建了一个线程对象
可运行的：线程对象创建完成后，其它线程调用了该线程的start()方法.
运行：可运行状态下的线程获得了CPU时间片，执行程序代码
阻塞：线程因为某些原因放弃了CPU的使用权。暂时停止运行，直到到达可运行的状态。阻塞又可分为
等待阻塞，即调用了线程的wait方法；
同步阻塞：运行的线程在获取对象的同步锁时，如果该同步锁被其它线程占用，该线程就会被JVM放入锁池中。
其它阻塞：如调用了线程的sleep方法，或者发出IO请求时
死亡，因为代码执行结束或发生异常退出后，线程就死亡了，这是不可逆的。

算法：判断一个序列是不是二叉查找树的后序遍历

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

解析：
二叉查找树有一个特定，左子树中的值都小于根节点，右子树的值都大于根节点。我们可以根据这个来递归判断。后序遍历序列的结构是左子树+右子树+根节点。找到根节点后递归按二叉树的特点判断即可。

解法：

public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null||sequence.length==0){
            return false;
        }
        return help(sequence,0,sequence.length-1);
    }

    public boolean help(int[] seq,int  begin,int end){
        if(begin>=end){
            return true;
        }
        int root=seq[end];
        int i=0;
        //寻找左右子树的分界点
        for(i=begin;i<end;i++){
            if(seq[i]>root){
                break;
            }
        }
        //判断右子树有无小于root的值
        for(int j=i;j<end;j++){
            if(seq[j]<root){
                return false;
            }
        }
        return help(seq,begin,i-1)&&help(seq,i,end-1);
        
    }