完全二叉樹特點

完全二叉樹是指除了最后一層之外，其他每一層的結點數都是滿的。最后一層如果也滿了，是一顆滿二叉樹，也是完全二叉樹。最后一層如果不滿，缺少的結點也全部的集中在左邊，那也是一顆完全二叉樹。

判斷一棵二叉樹是否為完全二叉樹

import java.util.*; class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } public class CheckCompletion { public boolean checking(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); boolean leaf = false; // 葉子結點 TreeNode left; TreeNode right; queue.add(root); while (!queue.isEmpty()) { root = queue.poll(); left = root.left; right = root.right; if ((leaf&&(left!=null||right!=null)) || (left==null&&right!=null)) { // 如果之前層遍歷的結點沒有右孩子，且當前的結點有左或右孩子，直接返回false // 如果當前結點有右孩子卻沒有左孩子，直接返回false return false; } if (left != null) { queue.offer(root.left); } if (right != null) { queue.offer(root.right); }else { leaf = false; // 如果當前結點沒有右孩子，那么之后層遍歷到的結點必須為葉子結點 } } return true; } }