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

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

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

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

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

定义如下递归函数头:

(1)另root = end-1,则arr[root]为从start开始,end结束的子树的根(后序遍历么!)

(2)我们另i从start开始,一直++,直到碰到第一个arr[i]大于arr[root]的,那么此时的i已经位于右子树了。从start~i-1是左子树。

(3)显然从i~end-2是右子树,我们检查这段arr[j],如果有发现<arr[root]的,直接返回false。(右子树必须都大于根!)

(4)递归检查左子树 judge(arr, start, i-1) 和右子树 judge(arr, i, end-2)。如果某一个judge返回0,那么返回0,两个都1返回1。

(5)如果start==end时候,或者arr==NULL时(空树也是BST的一种!),可以直接返回1。

好了,代码如下:

Leave a Reply

Your email address will not be published.