實現(xiàn)的思想
后序遍歷的特點：根在最后輸出
二叉搜索樹的特點：根的值大于左子樹值鲁纠，小于右子樹值
算法實現(xiàn)：
① 后序遍歷數(shù)組最后面的值為整棵樹的根root
② 遍歷數(shù)組找到當(dāng)前值比根root小并且后一個值大于根root的索引
③ 若數(shù)組為后續(xù)遍歷霍掺，則索引后面的值都應(yīng)該大于根root，若找到小于根root谎柄，則返回false
④ 若第③步不為false則遞歸的形參更新為左右子樹數(shù)組索引繼續(xù)重復(fù)②和③步驟。
public class Main
{
public static void main(String[] args)
{
//int[] arr={5,7,6,9,11,10,8};
int[] arr={4,7,5,9,13,11,8};
System.out.println(isProOfBST(arr,0, arr.length-1));
}
public static boolean isProOfBST(int[] arr,int left, int end)
{
if(arr == null || left > end) return false;
int root = arr[end];//后序遍歷的最后一個為根節(jié)點
int i = left;
while(arr[i] < root && i < end)//找到左樹的個數(shù)
i++;
int j = i;//先看右樹中是否有非法數(shù)字惯雳，即比根節(jié)點小的數(shù)字
while(j < end)
{
if(arr[j] < root) return false;
j++;
}
if(i == end) return true; //如果尋找結(jié)果發(fā)現(xiàn)最后只有左右葉子節(jié)點，則返回true
return isProOfBST(arr, left, i-1) && isProOfBST(arr, i, end-1);
}
}
