Java如何判斷一個數組是否為后序遍歷結果

本篇內容主要講解“Java如何判斷一個數組是否為后序遍歷結果”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Java如何判斷一個數組是否為后序遍歷結果”吧!

輸入一個整數數組，判斷該數組是不是某二元查找樹的后序遍歷的結果。如果是返回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;
    }
}

到此，相信大家對“Java如何判斷一個數組是否為后序遍歷結果”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！