Tag Archives: 二叉查找树

判断整数序列是不是二叉查找树(BST)的后序遍历结果

这里沿用传统二叉查找树(BST)的概念:所有左子树都小于根,右子树都大于根。(不止是直接孩子,还有间接孩子!)

现在给出一个整数序列,要求判断它是否是一棵二叉查找树BST的后序遍历结果。

如果去掉BST这个条件,我们一般是不能只根据后序遍历结果来确定某一棵树的。

有了BST这个条件后,我们可以这么做:

定义如下递归函数头:
int judge(int* arr, int start, int end)
(1)另root = end-1,则arr[root]为从star[......]

继续阅读