【摘要】：对于结点4的左子树遍历的序列{1，3，2}以及右子树的遍历序列{5，7，6}可以采用同样的方法来分析，因此，可以通过递归方法来实现，实现代码如下：程序的运行结果如下：1 3 2 5 7 6 4是某一二元查找树的后序遍历序列算法性能分析：这种方法对数组只进行了一次遍历，因此，时间复杂度为O。
【出自ALBB面试题】
难度系数：★★★★☆ 被考察系数：★★★★☆
题目描述：
输入一个整数数组，判断该数组是否是某二元查找树的后序遍历的结果。如果是，那么返回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}可以采用同样的方法来分析，因此，可以通过递归方法来实现，实现代码如下：(www.xing528.com)
程序的运行结果如下：
1 3 2 5 7 6 4是某一二元查找树的后序遍历序列
算法性能分析：
这种方法对数组只进行了一次遍历，因此，时间复杂度为O（N）。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
