方法一，采取标记的方法
非完全二叉树的三种情况
思路分析：
通过层序遍历来遍历树中的每一个非空结点
遍历到的每一个结点都分为四种情况 1.既有左孩子也有右孩子 操作：将左孩子和右孩子入队列 2.只有左孩子 操作： 1.首先判断标记是否处于激活状态，如果标记处于激活状态，直接返回 false2.满足标记条件，将标记设置为激活状态 3.只有右孩子 操作：直接返回 false，如果没有左结点而没有右结点，肯定不是一颗完全二叉树 4.没有孩子结点 操作：激活标记实现代码
/** * 判断一棵二叉树是否是完全二叉树 * * @return 如果是返回 true，否则返回 false */ public boolean isCompleteTree() { if (root == null) return true; return isCompleteTree(root); } /** * 通过层序遍历来遍历树中的每一个非空结点 * <p> * 每一个结点都分为四种情况 * 1.既有左孩子也有右孩子 * 操作：将左孩子和右孩子入队列 * 2.只有左孩子 * 操作： * 1.首先判断标记是否处于激活状态，如果标记处于激活状态，直接返回 false * 2.满足标记条件，将标记设置为激活状态 * 3.只有右孩子 * 操作：直接返回 false，如果没有左结点而没有右结点，肯定不是一颗完全二叉树 * 4.没有孩子结点 * 操作：激活标记 * <p> * 判断一棵二叉树是否是完全二叉树的实现 * * @param root 根节点 * @return 如果是返回 true，否则返回 false */ private boolean isCompleteTree(Node<T> root) { // 申请一个队列 ArrayDeque<Node<T>> queue = new ArrayDeque<>(); // 将根节点添加进去 queue.add(root); // 定义一个临时结点，存储的值为队列的队头结点 Node<T> head; // 定义一个标记，标记当前访问的结点出度是否为 2 ，如果结点只有左节点而没有右结点 flag = true boolean flag = false; while (!queue.isEmpty()) { // 执行出队列操作 head = queue.pop(); // 如果结点的左子树为空但右子树不为空，此时不满足完全二叉树的条件，直接返回 false if (head.left == null && head.right != null) return false; // 如果标志为 true，并且当前结点的左孩子结点不为空 if (flag && head.left != null) return false; // 如果当前结点的出度不为 2 if (head.left == null || head.right == null) flag = true; // 当前结点的左孩子不为空 if (head.left != null) queue.add(head.left); // 当前结点的右孩子不为空 if (head.right != null) queue.add(head.right); } return true; } 方法二，值为 null 的结点标记法一颗完全二叉树
一颗非完全二叉树
思路分析：
通过层序遍历来遍历树中的每一个结点采取特殊结点值为 null 替代 null 结点，入队列的标记方法每一个结点分为两种情况 如果当前结点不为空，直接将当前结点入队列如果当前结点为空，将结点值为 null 的标记结点入队列 当出队列的结点的值为标记结点 null 时，终止循环接着循环队列，条件为队列不为空，进行出队列操作，当出现队列出的结点的值不为 null 时，返回 false循环结束，返回 true，说明是一个完全二叉树实现代码
/** * 判断一棵树是否是一个完全二叉树 * * @return 如果是返回 true，否则返回 false */ public boolean isCompleteTree2() { if (root == null) return true; return isCompleteTree2(root); } /** * 通过层序遍历来遍历树中的每一个结点 * <p> * 采取特殊结点值为 null 替代 null 结点，入队列的标记方法 * <p> * 每一个结点分为两种情况 * 1.如果当前结点不为空，直接将当前结点入队列 * 2.如果当前结点为空，将结点值为 null 的结点入队列 * <p> * 当出队列的结点的值为标记结点 null 时，终止循环 * <p> * 接着循环队列，条件为队列不为空，进行出队列操作， * 当出现队列出的结点的值不为 null 时，返回 false * 循环结束，返回 true，说明是一个完全二叉树 * <p> * <p> * 判断一棵二叉树树是否是一颗完全二叉树的实现方法 * * @param root 根节点 * @return 如果是返回 true，否则返回 false */ private boolean isCompleteTree2(Node<T> root) { // 定义一个泛型为 Node 类型的队列 ArrayDeque<Node<T>> queue = new ArrayDeque<>(); // 将根节点入队列 queue.offer(root); // 定义一个结点，值为队列的头一个 Node<T> node = queue.peek(); // 当结点的值为 标记节点 null 的时候，直接退出循环 while (null != node.value) { queue.pop(); // 如果结点的左孩子不为 null，将左孩子入队列 // 否则插入一个值为 null 的 Node 对象 queue.offer(node.left != null ? node.left : new Node<>(null)); // 如果结点的左孩子不为 null，将左孩子入队列 queue.offer(node.right != null ? node.right : new Node<>(null)); node = queue.peek(); } while (!queue.isEmpty()) if (queue.pop().value != null) return false; return true; }