判断一个数组是否为后序遍历结果

输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。 思路一： 中序遍历为增长数组，判断是否矛盾 思路二： 如5、7、6、9、11、10、8 代码编写具体思路： 1.找到第一个大于根节点的数，即9，所以9之后的为右子树 2.如果右子树的值都大于根节点8，则符合 3.递归法分别判断是否左子树和右子树都符合这种特点。

package com.lifeibigdata.algorithms.blog;

import java.util.Arrays;

/**
 * 
 * 5、7、6、9、11、10、8
 *      8
    /      
   6       10
  /      / 
 5   7   9  11

 */
public class SearchTree {
    public static void main(String[] args) {
//        int[] a = {5,7,6,9,11,10,8};  //true
        int a[] = {7, 4, 6, 5} ;     //false
        System.out.println(searchTree(a,a.length)) ;

    }
    static boolean searchTree(int[] a,int length){
        if (a == null || length <= 0){
            return false;
        }
        boolean flag = true;
        int root = a[length - 1];
        int i = 0;
        while (a[i] < root){
            i++;           //得到左子树和右子树的分界线，a[i]为右子树第一个
        }
        int j = i;
        for (;j < length - 1; ++j){
            if (a[j] < root){
                flag = false;
            }
        }
        if (i > 0){
            searchTree(a,i);
        }
        if (i < length -1){
            searchTree(Arrays.copyOfRange(a,i,length -1),length -i - 1);
        }
        return flag;
    }
}

输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。 思路一： 中序遍历为增长数组，判断是否矛盾 思路二： 如5、7、6、9、11、10、8 代码编写具体思路： 1.找到第一个大于根节点的数，即9，所以9之后的为右子树 2.如果右子树的值都大于根节点8，则符合 3.递归法分别判断是否左子树和右子树都符合这种特点。 package com.lifeibigdata.algorithms.blog; import java.util.Arrays; /** * * 5、7、6、9、11、10、8 * 8 / 6 10 / / 5 7 9 11 */ public class SearchTree { public static void main(String[] args) { // int[] a = {5,7,6,9,11,10,8}; //true int a[] = {7, 4, 6, 5} ; //false System.out.println(searchTree(a,a.length)) ; } static boolean searchTree(int[] a,int length){ if (a == null || length <= 0){ return false; } boolean flag = true; int root = a[length - 1]; int i = 0; while (a[i] < root){ i++; //得到左子树和右子树的分界线，a[i]为右子树第一个 } int j = i; for (;j < length - 1; ++j){ if (a[j] < root){ flag = false; } } if (i > 0){ searchTree(a,i); } if (i < length -1){ searchTree(Arrays.copyOfRange(a,i,length -1),length -i - 1); } return flag; } }