关于完全二叉树判定的实例分析

简介：
本文通过具体实例探讨和分析了如何判断一棵给定的树是否为完全二叉树。通过对多种场景的应用示例进行详细解析，旨在帮助读者深入理解完全二叉树的特点及其判定方法。 完全二叉树是一种特殊的结构，在这种结构下除了最后一层外每一层的节点都必须填满，并且如果最后一层不满，则所有的节点都要靠左排列。而满二叉树则是所有层级均被完整填充的情况。 在定义一棵二叉树时，通常会使用一个`TreeNode`类来表示每个节点。这个类包括了该节点的值（val）、左侧子节点（left）和右侧子节点（right）的信息。 判断是否为完全二叉树可以通过层次遍历的方法实现，即广度优先搜索(BFS)。这可通过队列(Queue)的数据结构来完成：首先将根节点加入到队列中开始处理；在每次循环里取出当前层的首个元素，并检查其左右子节点是否存在。 于`CheckCompletion`类中的`checking`方法内设有一个布尔变量`leaf`，用于记录前一层是否为叶节点。如果上一层是叶节点，则本层不能再有非空子树存在；反之则可以继续扩展新的分支。同时，若发现某结点仅有右孩子而无左孩子的状况时亦视为不符合完全二叉树的定义。 在遍历过程中不断将找到的新节点添加进队列以备后续处理；一旦遇到某个当前层的节点仅拥有右侧子节点的情况，则需更新`leaf`为false表示接下来的所有层级都必须是叶结点。在整个检查流程中，如果发现任何违背完全二叉树规则的情形则立即返回结果为否。 当整个遍历完成后若未出现违规情况则最后确认该给定的二叉树符合完全二叉树的标准并输出true作为最终答案。 此方法的时间复杂度是O(n)，其中n代表总节点数，因为每个结点仅被访问一次；空间复杂度同样为O(n) ，最坏情况下整个队列可能容纳所有层级的所有非空子树元素。 综上所述，在判定一棵二叉树是否符合完全二叉树定义时关键在于理解其特性并使用层次遍历方式进行逐层检查，通过上述实现可以有效确认给定的结构满足要求与否。