By

文章目录
  1. 1. 题目
  2. 2. 解析
  3. 3. 代码
  4. 4. 参考

题目

输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。 如果是返回 true,否则返回 false。
例如输入 5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
      8 
     / \
    6  10 
   /\   /\ 
  5  7 9  11
因此返回 true。
如果输入 7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回 false

解析

做该题之前还必须得了解什么是二叉查找树
最主要的性质就是左子树的任何节点都小于根节点，右子树的任何节点都大于根节点。
然后后序遍历的最后一位肯定是根节点，所以，可以得到巧妙的方法为：
则该序列的最后一位a[n-1]必定是根节点，然后前面的序列中连续一部分是左子树的遍历，另一部份是右子树的遍历
此时需要在前面的序列中查找第一个大于root的节点a[i]

来个例子：后序遍历5、7，6，9，11，10，8
第一次迭代：根节点为8 然后从左遍历过来可以发现9为首个大于8的地方，那么如果再9后面的都大于8的话就可以判断9以及后面的为8的右子树
此时成立，8的左子树为5,7,6 右子树为9,11,10
第二次迭代：
左子树  6为根节点  同理7为6的右子树，5为6的左子树
右子树  10为根节点  同理11为10的右子树 9为11的左子树
剩余各个左右子树的各个孩子节点都为空，迭代停止，该序列为后序遍历

再来看7、4，6，5
其中5为根节点，7为第一个大于5的节点，但是7之后的4小于5，所以7以及后面的数字不可能为5的右子树，同时又不可能为左子树，所以不成立

代码

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
32
33
34
/**
 * 通过左右子树的递归序列判断他们是否也能构成二叉查找树即可
 * @param a
 * @param left
 * @param right
 * @return
 */
public static boolean isBSTPostOrder(int[] a,int left,int right)
{
	//这两个小于0的判断都是因为仅存在左子树 或者 仅存在右子树的时候 存在left必定会大于right
	if(left>=right)
		return true;
	
	int root=a[right];
	int mid=-1;
	for(int i=left;i<right;i++)
	{
		if(mid!=-1)
		{
			if(a[i]<root)
				return false;//第一个大于root后面的节点存在小于root的节点  直接返回false
		}else if(a[i]>root)
		{
			mid=i;//查找第一个大于root的值
			
		}
	}
	
	if(mid==-1)
		mid=right;//表示只有左子树
	
	//分别递归左右子树
	return isBSTPostOrder(a,left,mid-1) && isBSTPostOrder(a,mid,right-1);
}

测试代码

1
2
3
4
int[] a={5,7,6,9,11,10,8};//ok
int[] b={7,4,6,5};//not ok
System.out.println(isBSTPostOrder(a,0,a.length-1));
System.out.println(isBSTPostOrder(b,0,b.length-1));

true
false

参考

July 微软面试100题 第9题

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

文章目录
  1. 1. 题目
  2. 2. 解析
  3. 3. 代码
  4. 4. 参考