考察點

二叉搜索樹，樹的后序遍歷

知識點

題目

分析
本題目要求判斷某序列是否是二叉搜索樹的后序遍歷序列，后序遍歷的特點是左右根，因此序列的最后一個元素肯定是根結點，而前面的序列可以分為倆部分，第一部分是左子樹的序列，第二部分是右子樹的序列，所以一看到后序遍歷序列第一時間一定要想到這個序列的這個特點。又因為這顆樹是一顆二叉搜索樹，那么二叉搜索樹的特點就是左子樹一定比根結點小，右子樹一定比根結點大，我們利用好這個特點就可以很好的判斷這個序列是否滿足需求了，我們可以先遍歷序列找到第一個比根結點大的元素，可以確定的是如果這個序列是后序遍歷序列的話那么這個元素開始往后的元素一定都比根結點要大，一旦出現比根結點小的就可以斷定這個序列不符合需求。然后我們遞歸處理這個序列即可。同時遍歷的時候一定要注意根結點已經遍歷過了，每次遍歷都要把根結點去掉

public class TwentyFour {public static void main(String[] args) {int[] arr = {5,7,6,9,11,10,8};System.out.println(isAfterSquence(arr,0,arr.length - 1));int[] brr = {5,7,6,9,11,18};System.out.println(isAfterSquence(brr,0,brr.length - 1));int[] crr = {7,4,6,5};System.out.println(isAfterSquence(crr,0,crr.length - 1));}public static boolean isAfterSquence(int[] arr,int start,int end) {if (arr == null) {return false;}if (start >= end) {return true;}int root = arr[end];int rightIndx = start;for (int i = start;i <= end - 1;i++,rightIndx++) {if (arr[i] > root) {break;}}for (int j = rightIndx;j <= end - 1;j++) {if (arr[j] < root) {return false;}}return isAfterSquence(arr,start, rightIndx - start - 1) && isAfterSquence(arr,rightIndx,end - 1);}
}