判断一棵树是否是完全二叉树
程序员文章站
2022-05-16 11:23:13
...
一边对二叉树进行BFS将每一个节点都加入到队列,一边执行下面的判断
- 当前节点有右孩子,但没有左孩子,直接返回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 (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;
}