## 完全二叉树 ### 定义 完全二叉树是满二叉树的一部分，1到h-1层是满二叉树，h层节点集中在左边。 ### 判断完全二叉树 false判定条件 * 如果右节点不空，左节点空，不是完全二叉树 * 如果是叶子节点，且有左右节点的，不是完成二叉树 ~~~ /** * 判断 完全二叉树 * 完全二叉树是满二叉树的一部分，1到h-1层是满二叉树，h层节点集中在左边。 * @Author: mango * @Date: 2022/4/12 10:19 下午 */ public class CompleteTree { public boolean isCompleteTree(TreeNode root) { if(root == null){ return true; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); // 可能是叶子节点 boolean shouldBeLeaf = false; while (!queue.isEmpty()){ TreeNode cur = queue.poll(); // 如果右节点不空，左节点为空，则不是完全二叉树 if(cur.right != null && cur.left == null){ return false; } // 可能是叶子节点，且左节点或者右节点不为空的，则不是完全二叉树 if(shouldBeLeaf && (cur.left != null || cur.right != null)){ return false; } if(cur.left != null){ queue.offer(cur.left); }else{ shouldBeLeaf = true; } if(cur.right != null){ queue.offer(cur.right); }else{ shouldBeLeaf = true; } } return true; } } ~~~