## 完全二叉樹 ### 定義 完全二叉樹是滿二叉樹的一部分，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; } } ~~~