MENU

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

May 25, 2020 • Read: 258 • 算法

题目

有一棵二叉树,给定它的根节点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;
}
Archives Tip
QR Code for this page
Tipping QR Code