首先，什么是完全二叉树（complete binary tree）？

一、定义：

若设二叉树的深度为k，除第k层外，其他各层（1～（k-1）层）的节点数都达到最大值，且第k层所有的节点都连续集中在最左边，这样的树就是完全二叉树。如下图：

完全二叉树

完全二叉树是一种效率很高的数据结构，而堆是一种完全二叉树或者近似完全二叉树，因此堆的效率也很高；像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，二叉排序树的效率也要借助平衡性来提高，而平衡性是基于完全二叉树的。

下图是非完全二叉树：

非完全二叉树（第3层B节点的节点树没达到最大值）

二、特点

1) 在非空二叉树中，第k层的结点总数不超过2^(k-1)，k>=1;

2) 深度为k的二叉树最多有2k-1个结点(k>=1)，最少有k个结点;

3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;

4) 具有n个结点的完全二叉树的深度为log2(n+1);

5)有n个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

a、若m为结点编号则 如果m>1，则其父结点的编号为m/2；

b、如果2*m<=n，则其左儿子（即左子树的根结点）的编号为2*m；若2*m>n，则无左儿子；

c、如果2*m+1<=n，则其右儿子的结点编号为2m+1；若2m+1>n，则无右儿子。

6）给定n个节点，能构成h(n)种不同的二叉树，其中h(n)为卡特兰数的第n项，h(n)=C(2*n, n)/(n+1)。

7）设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i。

三、判断

 public boolean isCompleteTree(TreeNode root) { Queue<TreeNode> bfs = new LinkedList<TreeNode>(); bfs.offer(root); while (bfs.peek() != null) { TreeNode node = bfs.poll(); bfs.offer(node.left); bfs.offer(node.right); } while (!bfs.isEmpty() && bfs.peek() == null) bfs.poll(); return bfs.isEmpty(); }