二叉树的后续遍历序列

问题描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后续遍历的结果。如果是，则输出true，否则返回false

思路分析

如{5,7,6,9,11,10,8}，根据二叉排序树的后续遍历特点，首先知道最后一个数是根结点，然后让前面的数与它比较，当到某一个数大于他时，那门这个数的前面就是左子树，右边就是右子树，比如{5,7,6}为左子树，{9,11,10}为右子树，接着判断如果右子树中有存在某个数小于根结点8，也就是返回false，如果不是，在将左子树和右子树依次递归

码上有戏

public class BinaryOfOut {

	public boolean IsBianry(int[] ids){
		if(ids.length<0)
			return false;
		 int root=ids[ids.length-1];
		    int i=0;
		     for(;i<ids.length-1;i++)
		     {
		    	 if(ids[i]>root)
		    		 break;
		     }
		     int[] leftTree=new int[i];
               System.arraycopy(ids, 0, leftTree, 0,i);
               int j=i;
               for(;j<ids.length-1;j++)
               {
            	   if(root>ids[j])
            		   return false;
               }
               int[] rightTree=new int[ids.length-1-i];
                System.arraycopy(ids, i, rightTree, 0,ids.length-1-i);
               boolean leftFlag=true;
                if(i>0){
                	leftFlag=IsBianry(leftTree);
                }
                boolean rightFlag=true;
                if(i<ids.length-1){
                	rightFlag=IsBianry(rightTree);
                }
                return leftFlag&&rightFlag;
	}
	
	public static void main(String[] args) {
		
		System.out.println(new BinaryOfOut().IsBianry(new int[]{5,7,6,9,11,10,8}));
		System.out.println(new BinaryOfOut().IsBianry(new int[]{7,4,6,5}));

	}

}