给定一个序列，判断该序列是否为二叉查找树的后序遍历序列

问题

给出一个序列，判断该序列是否为二叉查找树的后序遍历序列。我们知道，二叉查找树中序遍历是有序的。也就是说，给定了后序遍历序列，其实就知道了中序遍历序列。因为，把后序遍历序列排序就得到了中序遍历序列。
又因为，中序遍历序列和后序遍历序列可以唯一确定一颗二叉树，故：给定一个序列，从理论上就证明了：可以判断该序列是否是二叉查找树的后序遍历序列。

分析

对于二叉树的先序遍历序列，第一个元素是根节点，后面剩余的元素分为连续的两部分：前面的一部分是根的左子树中的节点元素，后面的另一部分是根的右子树中的结点元素。
对于二叉树的后序遍历，最后一个元素是根结点，后面剩余的元素分为连续的两部分：前面的一部分是根的左子树中的结点元素，后面的另一部分是根的右子树中的结点元素。因为，后序遍历就是先访问根的左子树，再访问根的右子树，最后再访问根结点。
因此，基于此，就可以判断一个给定的序列是不是二叉查找树的后序遍历序列了

• 若右子树对应的序列中有比根小的元素，则它不是后序遍历序列；同理左子树
• 若相对于树根结点而言，左右子树对应的后序遍历序列第一点，则进一步递归判断左子树和右子树对应的序列是否还满足，直到判断到叶结点为止。