Question

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。

例如输入数组{5,7,6,9,11,10,8}，则返回true，因为这个整数序列是图4.6二叉搜索树的后序遍历结果。如果输入的数组是{7,4,6,5}，由于没有哪棵二叉搜索树的后序遍历的结果是这个序列，因此返回false。

图4.6　后序遍历序列5、7、6、9、11、10、8对应的二叉搜索树

在后序遍历得到的序列中，最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分：第一部分是左子树结点的值，它们都比根结点的值小；第二部分是右子树结点的值，它们都比根结点的值大。

以数组{5,7,6,9,11,10,8}为例，后序遍历结果的最后一个数字8就是根结点的值。在这个数组中，前3个数字5、7和6都比8小，是值为8的结点的左子树结点；后3个数字9、11和10都比8大，是值为8的结点的右子树结点。

我们接下来用同样的方法确定与数组每一部分对应的子树的结构。这其实就是一个递归的过程。对于序列5、7、6，最后一个数字6是左子树的根结点的值。数字5比6小，是值为6的结点的左子结点，而7则是它的右子结点。同样，在序列9、11、10中，最后一个数字10是右子树的根结点，数字9比10小，是值为10的结点的左子结点，而11则是它的右子结点。

我们再来分析另一个整数数组{7,4,6,5}。后序遍历的最后一个数是根结点，因此根结点的值是5。由于第一个数字7大于5，因此在对应的二叉搜索树中，根结点上是没有左子树的，数字7、4和6都是右子树结点的值。但我们发现在右子树中有一个结点的值是4，比根结点的值5小，这违背了二叉搜索树的定义。因此不存在一棵二叉搜索树，它的后序遍历的结果是7、4、6、5。

找到了规律之后再写代码，就不是一件很困难的事情了。下面是参考代码：

源代码：

本题完整的源代码详见24_SquenceOfBST项目。

测试用例：

- 功能测试（输入的后序遍历的序列对应一棵二叉树，包括完全二叉树、所有结点都没有左/右子树的二叉树、只有一个结点的二叉树；输入的后序遍历的序列没有对应一棵二叉树）。

- 特殊输入测试（指向后序遍历序列的指针为NULL指针）。

本题考点：

- 考查分析复杂问题的思维能力。能否解决这道题的关键在于应聘者是否能找出后序遍历的规律。一旦找到规律了，用递归的代码编码相对而言就简单了。在面试的时候，应聘者可以从一两个例子入手，通过分析具体的例子寻找规律。

- 考查对二叉树后序遍历的理解。

相关题目：

输入一个整数数组，判断该数组是不是某二叉搜索树的前序遍历的结果。这和前面问题的后序遍历很类似，只是在前序遍历得到的序列中，第一个数字是根结点的值。

举一反三：

如果面试题是要求处理一棵二叉树的遍历序列，我们可以先找到二叉树的根结点，再基于根结点把整棵树的遍历序列拆分成左子树对应的子序列和右子树对应的子序列，接下来再递归地处理这两个子序列。本面试题是应用这个思路，面试题6重建二叉树也是应用这个思路。