剑指offer面试题24 二叉树搜索树的后续遍历序列

考察点

二叉搜索树，树的后序遍历
1

知识点

题目

分析
本题目要求判断某序列是否是二叉搜索树的后序遍历序列，后序遍历的特点是左右根，因此序列的最后一个元素肯定是根结点，而前面的序列可以分为俩部分，第一部分是左子树的序列，第二部分是右子树的序列，所以一看到后序遍历序列第一时间一定要想到这个序列的这个特点。又因为这颗树是一颗二叉搜索树，那么二叉搜索树的特点就是左子树一定比根结点小，右子树一定比根结点大，我们利用好这个特点就可以很好的判断这个序列是否满足需求了，我们可以先遍历序列找到第一个比根结点大的元素，可以确定的是如果这个序列是后序遍历序列的话那么这个元素开始往后的元素一定都比根结点要大，一旦出现比根结点小的就可以断定这个序列不符合需求。然后我们递归处理这个序列即可。同时遍历的时候一定要注意根结点已经遍历过了，每次遍历都要把根结点去掉

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);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31