PAT 解题报告 (数据结构学习与实验指导) 4-06. 搜索树判断

题目描述:

对于二叉搜索树,我们规定任一结点的左子树仅包含严格小于该结点的键值,而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树,得到的树叫做镜像二叉搜索树。

现在我们给出一个整数键值序列,请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列,如果是,则输出对应二叉树的后序遍历序列。

算法分析:

对于先序遍历, 第一个数字肯定是我们的root, 然后扫一遍, 找到第一个比root大的数字, 记录下index, 那么从preorder[1]…preorder[index-1]就是我们的左子树的先序遍历, 递归调用算法构造出二叉搜索树, preorder[index]…preorder[n-1]则是我们的右子树, 同样也是递归构造, 算法要么构造出一颗合法的二叉搜索树, 要们出现矛盾, 说明这个先序遍历不是合法的. 那么考虑可能这棵树是所谓的镜像二叉树, 同样也是递归构造, 只不过现在的左子树全部包含了大于或者等于根的数字, 右子树包含了严格小于根的数字. 这样对于每一个node而言都要扫面一边数组, 整体算法复杂度是O(N^2), N <= 1000, 故可以解决问题,

注意点:

网上可以找到传说中的O(N)构建还原二叉树的方法, 还没看懂, 看懂了再来更新.

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on August 1, 2013