完全二叉樹是指除了最后一層之外，其他每一層的結(jié)點(diǎn)數(shù)都是滿的,今天百分網(wǎng)小編為大家整理的判斷二叉樹是否為完全二叉樹的實(shí)例，僅供學(xué)習(xí)參考，歡迎大家閱讀瀏覽！

 

　　完全二叉樹特點(diǎn)

 

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

 

　　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é)點(diǎn)

 

　　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é)點(diǎn)沒有右孩子，且當(dāng)前的結(jié)點(diǎn)有左或右孩子，直接返回false

 

　　// 如果當(dāng)前結(jié)點(diǎn)有右孩子卻沒有左孩子，直接返回false

 

　　return false;

 

　　}

 

　　if (left != null) {

 

　　queue.offer(root.left);

 

　　}

 

　　if (right != null) {

 

　　queue.offer(root.right);

 

　　}else {

 

　　leaf = false; // 如果當(dāng)前結(jié)點(diǎn)沒有右孩子，那么之后層遍歷到的結(jié)點(diǎn)必須為葉子結(jié)點(diǎn)

 

　　}

 

　　}

 

　　return true;

 

　　}

 

　　}

 

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