3.7 如何判断一个数组是否是二元查找树后序遍历的序列

难度系数：★★★☆☆　被考察系数：★★★★☆

题目描述：

输入一个整数数组，判断该数组是否是某二元查找树的后序遍历的结果。如果是，那么返回true，否则返回false。例如数组{1，3，2，5，7，6，4}就是下图中二叉树的后序遍历序列。

分析与解答：

二元查找树的特点是：对于任意一个结点，它的左子树上所有结点的值都小于这个结点的值，它的右子树上所有结点的值都大于这个结点的值。根据它的这个特点以及二元查找树后序遍历的特点，可以看出，这个序列的最后一个元素一定是树的根结点（上图中的结点4），然后在数组中找到第一个大于根结点4的值5，那么结点5之前的序列（1，3，2）对应的结点一定位于结点4的左子树上，结点5（包含这个结点）后面的序列一定位于结点4的右子树上（也就是说结点5后面的所有值都应该大于或等于4）。对于结点4的左子树遍历的序列{1，3，2}以及右子树的遍历序列{5，7，6}可以采用同样的方法来分析，因此，可以通过递归方法来实现，实现代码如下：

程序的运行结果为

算法性能分析：

这个方法对数组只进行了一次遍历，因此，时间复杂度O（n）。