1110 Complete Binary Tree (25 point(s))-白红宇的个人博客

1110 Complete Binary Tree (25 point(s))

发布日期：2021-05-18 12:17:44 浏览次数：10 分类：精选文章

本文共 547 字，大约阅读时间需要 1 分钟。

根据完全二叉树的性质，层序依次给定编号1~n；如果最大编号与n相等，则是完全二叉树。完全二叉树的判断涉及树的遍历和节点的填充情况。以下是详细分析：

完全二叉树的定义：完全二叉树除了最后一层可能不满之外，每一层从左到右的节点数目都达到最大。为了判断给定的二叉树是否为完全二叉树，可以通过遍历树，并记录树的最大深度和最后一个访问的节点。

输入处理：将输入的节点及其子节点信息存储在数组中。使用两个数组l和r分别存储左右子节点的位置。检查数组check用于记录每个节点的子节点数。

根节点的确定：找出所有子节点数为0的节点作为根节点。通常整个树只有一个根节点。

深度优先搜索：通过递归深度优先搜索遍历树，记录每个节点，并更新最大索引max_idx和最后访问的节点last。

判断完全二叉树：如果输入的节点数n等于最大索引max_idx，说明树是完全二叉树，返回“YES”并输出根节点的编号；否则返回“NO”。

以下测试示例：

通过这种方法，可以正确判断给定的二叉树是否为完全二叉树。

上一篇：1138 Postorder Traversal (25 point(s))

下一篇：1115 Counting Nodes in a BST (30 point(s))

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！