大家好，又见面了，我是你们的朋友全栈君。
完全二叉树的定义: 一棵二叉树，除了最后一层之外都是完全填充的，并且最后一层的叶子结点都在左边。
https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91/7773232?fr=aladdin
百度定义
思路：层序遍历二叉树
如果一个结点，左右孩子都不为空，则pop该节点，将其左右孩子入队列
如果一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树
如果一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空：：：：：则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则返回false。
非完全二叉树的例子（对应方法的正确性和必要性）：
下面写代码：
定义结点：
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}方法：
public static boolean isCBT(Node head) {
if (head == null) {
return true;
}
Queue<Node> queue = new LinkedList<Node>();
boolean leaf = false;
Node l = null;
Node r = null;
queue.offer(head);
while (!queue.isEmpty()) {
head = queue.poll();
l = head.left;
r = head.right;
if ((leaf && (l != null || r != null)) || (l == null && r != null)) {
return false;//当前结点不是叶子结点且之前结点有叶子结点 || 当前结点有右孩子无左孩子
}
if (l != null) {
queue.offer(l);
}
if (r != null) {
queue.offer(r);
} else {
leaf = true;//无孩子即为叶子结点
}
}
return true;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/158639.html原文链接：https://javaforall.net
