All About Programming: 解题笔记（7）――判断整数序列是不是二元查找树的后序遍历结果 - wuzhekai的专栏 - 博客频道

问题描述：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。

例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：

         8
      / /
     6    10
    / / / /
   5 7 9 11
因此返回true。如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。

思路：分析后序遍历的特点，序列的最后一个数应该是根结点，剩余的节点分为两个连续的子序列，前一子序列的值小于最后一个数，后一子序列的值大于最后一个数。然后递归求解这两个子序列。

如果是判断是前序遍历也很简单，只不过根节点变为了第一个数，剩余的节点也是分为两个连续的子序列。如果判断是中序遍历，更方便，只需扫描一遍，检查序列是不是排好序的，如果没有排好序，就不是中序遍历的结果

Labels