您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“Java如何判斷一個(gè)數(shù)組是否為后序遍歷結(jié)果”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“Java如何判斷一個(gè)數(shù)組是否為后序遍歷結(jié)果”吧!
輸入一個(gè)整數(shù)數(shù)組,判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。如果是返回true,否則返回false。
思路一:
中序遍歷為增長數(shù)組,判斷是否矛盾
思路二:
如5、7、6、9、11、10、8
代碼編寫具體思路:
1.找到第一個(gè)大于根節(jié)點(diǎn)的數(shù),即9,所以9之后的為右子樹
2.如果右子樹的值都大于根節(jié)點(diǎn)8,則符合
3.遞歸法分別判斷是否左子樹和右子樹都符合這種特點(diǎn)。
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]為右子樹第一個(gè) } 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如何判斷一個(gè)數(shù)組是否為后序遍歷結(jié)果”有了更深的了解,不妨來實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。