扣丁學(xué)堂Java培訓(xùn)告訴你如何判斷二叉樹是否為完全二叉樹

         近日有小伙伴詢問扣丁學(xué)堂的咨詢老師關(guān)于二叉樹方面的問題，小編發(fā)現(xiàn)有不少的小伙伴不知道如何判斷二叉樹是否為完全二叉樹，現(xiàn)在小編就給大家分享一下扣丁學(xué)堂Java在線學(xué)習(xí)講述的判斷二叉樹是否為完全二叉樹的實例。

完全二叉樹特點

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

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

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; // 葉子結(jié)點
    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)) {
        // 如果之前層遍歷的結(jié)點沒有右孩子，且當(dāng)前的結(jié)點有左或右孩子，直接返回false
        // 如果當(dāng)前結(jié)點有右孩子卻沒有左孩子，直接返回false
        return false;
      }
      if (left != null) {
        queue.offer(root.left);
      }
      if (right != null) {
        queue.offer(root.right);
      }else {
        leaf = false; // 如果當(dāng)前結(jié)點沒有右孩子，那么之后層遍歷到的結(jié)點必須為葉子結(jié)點
      }
    }
    return true;
  }
}

以上就是扣丁學(xué)堂Java培訓(xùn)小編為大家分享的如何判斷二叉樹是否為完全二叉樹，希望對小伙伴們有所幫助，想要了解更多內(nèi)容的小伙伴可以登錄扣丁學(xué)堂官網(wǎng)咨詢，扣丁學(xué)堂是專業(yè)的Java培訓(xùn)機(jī)構(gòu)，不僅有專業(yè)的老師和與時俱進(jìn)的課程體系，還有大量的Java視頻教程供學(xué)員觀看學(xué)習(xí)哦?？鄱W(xué)堂java技術(shù)交流群：487098661。微信號：codingbb