转载请注明原文地址：http://www.cnblogs.com/ygj0930/p/6611702.html
一：满二叉树
除了叶子结点无任何子节点外，每一层的结点都有两个子节点。也就是说：一棵满二叉树是一个完整的三角形 △ 结构。
满二叉树的性质：若满二叉树的层数为L，结点数为N，则： N=2^L-1。（结点数为 2的层数次方 减一）
二：完全二叉树
完全二叉树：1：一棵树，除了叶子节点那一层，上面的各层一定是满的。当最后一层也是满的，则树是完全二叉树也是满二叉树。
2：叶子结点那一层，结点严格按照“从左往右”插入。
判断完全二叉树==按层遍历（用队实现即可，由于无需具体层信息，所以不需last和newlast来控制层）二叉树，
对每个出队结点：判据一：如果有右儿子无左儿子，则返回false；
判据二：如果有左儿子无右儿子，则队中剩下的一定全是叶结点，对之后每个出队的元素判断是否为叶。若有否的，则返回false。
如果遍历过程无返回false，则该树是完全二叉树， 返回true。
public class CheckCompletion { public boolean chk(TreeNode root) { if(root==null){ return true; } LinkedList<TreeNode> queue=new LinkedList<TreeNode>(); queue.offer(root); TreeNode curr=null; //判据二：当处理到一个出队元素有左儿子但无右儿子时，则此后出队的元素全是叶结点。开始对此后每个出队元素进行叶结点判断 boolean leafbeg=false; while(!queue.isEmpty()){ curr=queue.poll(); //判据二 if(leafbeg){ if(!isLeaf(curr)){ return false; } } //判据一：有右儿子无左儿子，则直接返回false if(curr.left==null && curr.right!=null){ return false; } //如果有左无右，则开启判据二 if(curr.left!=null && curr.right==null){ queue.offer(curr.left); leafbeg=true; } //左右儿子全有，入队 if(curr.left!=null && curr.right!=null){ queue.offer(curr.left); queue.offer(curr.right); } } return true; } public boolean isLeaf(TreeNode node){ if(node.left!=null||node.right!=null){ return false; } return true; } }