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

题目

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

分析

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

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

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