秒懂【完全二叉树】判断！超清晰图解一步步拆解。

1.思路

先来看完全二叉树的定义：

完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）

通过层序遍历二叉树：先将节点入队列，之后取出节点，将节点对应的左右子树入队列，如此循环往复。（注意：左右子树为null也要入队列；null节点没有左右子树，因此不能对null节点的左右子树入队列。）判断方法：如果当前节点不为空，前面的（同一层或上几层）节点出现了空，因此则该二叉树不是完全二叉树。

对于二叉树的层序遍历，请参考前期文章《可视化图解算法：二叉树的层序遍历》。

对于如下的二叉树，进行层序遍历之后，结果集数据中对应的数据前面没有null，因此该二叉树是完全二叉树。

alt

对于如下的二叉树，进行层序遍历之后，结果集中的6前面出现了null，因此该二叉树是不是完全二叉树。

alt

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Python代码

class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        # write code here
        if root is None:
            return True
        my_queue = [root]  # 定义一个队列，保存每一层的所有节点；先将根节点放入队列
        null_node_exist = False  # 同一层级左边的节点是否为空，或者上一层级是否有空节点
        while len(my_queue) > 0:
            count = len(my_queue)  # 获取一层中的节点数量，并进行遍历
            for i in range(count):
                cur_node = my_queue[0]  # 获取队列的顶部元素
                my_queue = my_queue[1:]
                if cur_node is None:
                    null_node_exist = True  # 如果当前节点为空，更改标志位
                else:

                    if null_node_exist:
                        return False  # 当前节点不是空节点；而同一层级左边的节点为空，或者上一层级有空节点 则 不是完全二叉树

                    # 将左右子树都入队列（空值也入队列）
                    my_queue.append(cur_node.left)
                    my_queue.append(cur_node.right)
        # 所有层都遍历完了，说明是完全二叉树
        return True

2.2 Java代码

public static class Solution {
            /**
             * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
             *
             * @param root TreeNode类
             * @return bool布尔型
             */
            public boolean isCompleteTree(TreeNode root) {
                // write code here
                //如果节点为空，则为完全二叉树
                if (root == null) {
                    return true;
                }
                //队列存储，进行层次遍历
                ArrayList<TreeNode> queue = new ArrayList<>();
                queue.add(root);//先将根节点放入队列
                boolean nullNodeExist = false; //同一层级左边的节点是否为空，或者上一层级是否有空节点
                while (!queue.isEmpty()) {
                    int count = queue.size();//获取一层中的节点数量，并进行遍历
                    for (int i = 0; i < count; i++) {
                        TreeNode curNode = queue.remove(0);//获取队列的顶部元素;删除队列的顶部元素
                        if (curNode == null) {
                            nullNodeExist = true; //如果当前节点为空，更改标志位
                        } else {
                            if (nullNodeExist) {
                                return false; //当前节点不是空节点；而同一层级左边的节点为空，或者上一层级有空节点 则 不是完全二叉树
                            }
                            //将左右子树都入队列（空值也入队列）
                            queue.add(curNode.left);
                            queue.add(curNode.right);
                        }
                    }
                }
                // 所有层都遍历完了，说明是完全二叉树
                return true;
            }
}

2.3 Go代码

func isCompleteTree(root *TreeNode) bool { // write code here
	//如果节点为空，则为完全二叉树
	if root == nil {
		return true
	}
	//定义一个队列，将根节点入队列
	queue := []*TreeNode{root}
	nullNodeExist := false //同一层级左边的节点是否为空，或者上一层级是否有空节点
	for len(queue) > 0 {
		count := len(queue) //获取一层中的节点数量，并进行遍历
		for i := 0; i < count; i++ {
			curNode := queue[0] //获取队列的顶部元素
			queue = queue[1:]   //删除队列的顶部元素
			if curNode == nil {
				nullNodeExist = true
			} else {
				if nullNodeExist {
					return false //当前节点不是空节点；而同一层级左边的节点为空，或者上一层级有空节点 则 不是完全二叉树
				}
				//将左右子树都入队列（空值也入队列）
				queue = append(queue, curNode.Left)
				queue = append(queue, curNode.Right)
			}
		}
	}
	// 所有层都遍历完了，说明是完全二叉树
	return true
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构