判断二叉树是否为完全二叉树的实例

完全二叉树特点
完全二叉树是指除了最后一层之外，其他每一层的结点数都是满的。最后一层假设也满了，是一颗满二叉树，也是完全二叉树。最后一层假设不满，缺少的结点也全部的集中在左边，那也是一颗完全二叉树。
判断一棵二叉树是否为完全二叉树

1. import java.util.*;
2. class TreeNode {
3.   int val = 0;
4.   TreeNode left = null;
5.   TreeNode right = null;
6.   public TreeNode(int val) {
7.     this.val = val;
8.   }
9. }
10. public class CheckCompletion {
11.   public boolean checking(TreeNode root) {
12.     Queue<TreeNode> queue = new LinkedList<TreeNode>();
13.     boolean leaf = false; // 叶子结点
14.     TreeNode left;
15.     TreeNode right;
16.     queue.add(root);
17.     while (!queue.isEmpty()) {
18.       root = queue.poll();
19.       left = root.left;
20.       right = root.right;
21.       if ((leaf&&(left!=null||right!=null)) || (left==null&&right!=null)) {
22.         // 假设之前层遍历的结点没有右孩子，且当前的结点有左或右孩子，直接返回false
23.         // 假设当前结点有右孩子却没有左孩子，直接返回false
24.         return false;
25.       }
26.       if (left != null) {
27.         queue.offer(root.left);
28.       }
29.       if (right != null) {
30.         queue.offer(root.right);
31.       }else {
32.         leaf = false; // 假设当前结点没有右孩子，那么之后层遍历到的结点必需为叶子结点
33.       }
34.     }
35.     return true;
36.   }
37. }

复制代码

感激阅读，希望能协助到大家，谢谢大家对本站的支持！