数据结构题目，后续遍历

左手的ㄟ右手 2022-08-20 14:17 137阅读 0赞

判断一个给定的数组，是不是二叉树的后续遍历结果的思想是：

给定数组，数组最后一个借点值，坑定是根节点的值，从数组第一个节点开始，比根节点小的值一定是左子树节点，比根节点大的值一定是右子树节点。接着递归判断左子树的状况，例如第一个测试用例。｛5，7，6，9，11，10，8｝根节点为8.   5，7，6 都是左子树节点， 9 11 10 都是右子树节点。接着递归判断

package Abc;
    /**
     * 判断整数序列是不是二叉树的后续遍历结果
     * */
    public class Bestfor {
    	public static void main(String[] args){
    		int[] array={9,6,9};
    		if(isAfterResult(array,0,array.length-1)){
    			System.out.println("此数组符合二叉树的后序遍历");
    		}else{
    			System.out.println("此数组不符合二叉树的后序遍历");
    		}
    	}
    	//判断一个整数数组是不是二叉树的后序遍历结果，使用递归算法
    	private static boolean isAfterResult(int[] array,int start,int stop){
    		if(null == array){
    			throw new NullPointerException();
    		}
    		//判断一下start 和stop是否月结
    		if(start < 0 || start >array.length || stop <0 || stop >array.length || start >stop){
    			throw new ArrayIndexOutOfBoundsException();
    		}
    		//判断的时候分为三种情况，第一种情况当数组的长度小于3
    		//第二种情况当数组的长度等于3，判断数据的根节点，与头结点。
    		//第三种情况。当数组的长度大于3的情况，进行递归
    		int count= stop -start +1;
    		if(count < 3){
    			return true;
    		}else if(count == 3){
    			//等于3的情况，当根节点大于等于头结点，并且根节点小于等于第二个	元素		
    			if(array[stop] >= array[start] && array[stop]<= array[start+1]){
    				return true;
    			}else{
    				return false;
    			}
    		}else{
    			//循环遍历数组
    			int index=-1;
    			for(int i=start;i<stop;i++){
    				//如果第i个元素大于根节点的元素
    				if(array[i]>=array[stop]){
    					index=i;
    					break;
    				}
    			}
    			if(index == -1 || index ==0){
    				return isAfterResult(array,start,stop-1);
    			}else{
    				return isAfterResult(array,start,index-1) && isAfterResult(array,index,stop-1);
    			}
    		}
    	}
    
    }