PAT 解题报告 (数据结构学习与实验指导) 4-09. 笛卡尔树

题目描述:

笛卡尔树是一种特殊的二叉树,其结点包含两个关键字K1和K2。首先笛卡尔树是关于K1的二叉搜索树,即结点左子树的所有K1值都比该结点的K1值小,右 子树则大。其次所有结点的K2关键字满足优先队列(不妨设为最小堆)的顺序要求,即该结点的K2值比其子树中所有结点的K2值小。给定一棵二叉树,请判断 该树是否笛卡尔树。

算法分析:

在我看来这个题目有三个考察点:

(1) 构建array based 二叉树, 基于数组而不是指针, 那么下面的结构体就够用了

struct TreeNode {
int K1;
int K2;
int left;  //-1 indicates it is NULL
int right; //instead of TreeNode *right
};

(2) 检查一颗二叉树是不是二叉搜索树(BST), 这个问题其实非常容易掉进陷阱, 是不是很容易就想到递归? 对每个node测试left child < current node < right child, 然后递归调用测试left child和right child.如果你这样想的话, 你已经掉进了陷阱了, 那么考虑一下下面这个例子:

4
                  / \
                 3   7
                /\
               2  5

所以光检查一层是不够的, 正确的做法是比较左子树的最大值应当比当前node的K1值小, 右子树的最小值应当比当前node的键值大. 这个也可以用一次DFS完成, 也就是说一次DFS就能找到所有子树的最大最小, 时间复杂度是O(N), 如果你对每个node都去用dfs找一遍左右子树的最到最小的话效率是O(N^2), 怎么实现O(N)的算法留个大家自己思考一下:P 也可以留言讨论。

(3) 检查一棵树是不是一个最小堆. 这个比检查一颗二叉树是不是二叉搜索树简单多了, 直接递归就行了: 对每个node测试left child > current node && right child > current node. 大家可以比较一下为什么同样递归的思路这里就又正确了呢? 这个就是堆和二叉搜索树的性质的区别. 大家可以仔细体会一下.

注意点:

小心二叉搜索树(BST)的判断。

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


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

Written on July 28, 2013