判斷二叉樹是否為完全二叉樹的實例

完全二叉樹特點

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

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

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;
  }
}

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！