欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-16 11:23:13
...

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

  1. 当前节点有右孩子,但没有左孩子,直接返回false
  2. 当前节点有左孩子没右孩子 或者 当前结点左孩子右孩子都没有,那么接下来遇到的所有节点必须是叶子节点
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 (l == null && r != null)
            return false;
        //当取出的结点必须是叶子结点,而取出结点的左孩子或者右孩子不为空时,一定不是完全二叉树
        if (leaf && (l != null || r != null)){
			return true;
		}
        if (l != null)
            q.add(l);
        if (r != null)
            q.add(r);
        //else表示右孩子不为空,也就是说,当前节点有左孩子没右孩子 或者 
        //当前结点左孩子右孩子都没有,那么接下来遇到的所有节点必须是叶子节点
        else
            leaf = true;
    }
    return true;
}

相关标签: LeetCode