判断一棵树是否为完全二叉树

题目

有一棵二叉树，给定它的根节点root，请设计一个算法判断它是否是完全二叉树

分析

一边对二叉树进行BFS将每一个节点都加入到队列，一边执行下面的判断

当前节点有右孩子，但没有左孩子，直接返回false当前节点有左孩子没右孩子，那么接下来遇到的所有节点必须是叶子节点

例如下图所示的情况，当遍历到红色节点后，由于其只有左孩子，没有右孩子，因此实际上认为当前开启了一个状态，这个状态的开启，使得接下来的所有节点必须只能是叶子节点，如果不是，则该二叉树不是完全二叉树。例如，接下来访问到绿色节点，发现该节点不是叶子节点，因此直接返回false

代码

public static boolean check(Node head) { boolean leaf = false; // 是否开启了状态 Queue<Node> q = new LinkedList<Node>(); q.add(head); while (!q.isEmpty()) { Node cur = q.poll(); Node l = cur.lchild; Node r = cur.rchild; if ((leaf && (l != null && r != null)) || (l == null && r != null)) return false; if (l != null) q.add(l); if (r != null) q.add(r); else leaf = true; } return true; }