给定一棵二叉树的头节点head,返回这颗二叉树中是不是完全二叉树
什么是完全二叉树，一句话可以总结——这棵树的每一层，要么就是满的，要么就是从左到右依次变满的。
方法一
（网上最常见的，不用二叉树的递归套路）：宽度优先遍历这棵树，如有不了解宽度优先遍历的，可以看看这篇文章——二叉树的按层遍历。在宽度优先遍历二叉树的时候，做如下判断：
- 遇到的每一个结点，如果有右孩子，但是没有左孩子，一定不是完全二叉树。因为一定是要从左到右依次变满的。
- 一旦遇到第一个左右孩子不双全的结点，接下来遇到的所有结点，都必须是叶子结点。 这种情况下，一定是完全二叉树。
给大伙画棵树，大家自己对着上面两个条件判断一下。
方法二
二叉树的递归套路，二叉树的递归套路威力是无穷的，关键在于列可能性。判断一棵树是否为完全二叉树，我们以最后一层的最后一个结点到哪了进行分类。
1）无缺口：所有层都是满的，没有缺口位置（缺口就是最后一层成长到的位置。）这种情况下这棵树就是满二叉树。
此时，我们需要向左树要的信息是：（假设以X为头节点，下文也是）左树整体是否是满二叉树+左树的高度。 右树也一样。如果左右都是满二叉树的并且高度一样，那么以X为头节点的整颗树就是满二叉树。
2）有缺口：又有三种可能
1》：缺口停留在左树的位置，没有越过左树边界到右树上去。
满足这种情况需要的条件是：
左树整体是完全二叉树
&&
右树整体是满二叉树
&&
左树高度==右树高度+1
2》：左树成长情况是左树已经撑满了，右树全为空。
左树是满二叉树 && 右树是满二叉树 && 左树高度==右树高度+1
3》：最后一层成长的位置把左树撑满了，并且来到了右树上。
左树是满二叉树 && 右树是完全二叉树 && 左右高度一样
以上将所有可能性全部列了出来，如果四种情况都不成立，则必定不是完全二叉树，如果四个中有一个成立就是完全二叉树。
接下来进行整合，向每颗子树要的信息就是如下三个：
- 整颗子树是否是满二叉树
- 整颗子树是否是完全二叉树
- 整颗子树的高度
完整代码：
package com.harrison.class08; import java.util.LinkedList; import java.util.Queue; public class Code08_IsCBT { public static class Node { public int value; public Node left; public Node right; public Node(int data) { this.value = data; } } public static boolean isCBT1(Node head) { if(head==null) { return true; } Queue<Node> queue=new LinkedList<>(); queue.add(head); Node L=null; Node R=null; // 是否遇到左右两个孩子不双全的结点，一开始默认没有遇到 boolean leaf=false; while(!queue.isEmpty()) { head=queue.poll(); L=head.left; R=head.right; // 条件1：如果一旦遇到某个结点有右孩子但是没右左孩子(有右无左)，必定不是完全二叉树 // 条件2：如果遇到第一个左右孩子不双全的结点，接下来遇到的所有结点都必须是叶子节点， // 否则必定不是完全二叉树 if( (L==null && R!=null) || (leaf && (L!=null || R!=null)) ) { return false; } // 接下来开始玩宽度优先遍历 if(L!=null) { queue.add(L); } if(R!=null) { queue.add(R); } // 左右孩子有任何一个缺失，就说这个结点不双全，所以设置为true // 可能多次改为true，但不要紧，只要第一次从false改为true，之后永远都为true // 该判断只是为了说明：只要有两个孩子不双全的情况，这个遍历就要设置为true， // 其实只需要使用第一次设置为true的时候 if(L==null || R==null) { leaf=true; } } return true; } public static class Info{ public boolean isFull; public boolean isCBT; public int height; public Info(boolean full,boolean cbt,int h) { isFull=full; isCBT=cbt; height=h; } } public static Info process1(Node head) { if(head==null) { return new Info(true, true, 0); } Info leftInfo=process1(head.left); Info rightInfo=process1(head.right); int height=Math.max(leftInfo.height, rightInfo.height)+1; boolean isFull=leftInfo.isFull && rightInfo.isFull && leftInfo.height==rightInfo.height; boolean isCBT=false; if(isFull) { // 1）无缺口：所有层都是满的， // 没有缺口位置（缺口就是最后一层成长到的位置。）这种情况下这棵树就是满二叉树。 isCBT=true; }else { // 分别是情况2）的 1》、2》3》 if(leftInfo.isCBT && rightInfo.isCBT) { if(leftInfo.isCBT && rightInfo.isFull && leftInfo.height==rightInfo.height+1) { isCBT=true; } if(leftInfo.isFull && rightInfo.isFull && leftInfo.height==rightInfo.height+1) { isCBT=true; } if(leftInfo.isFull && rightInfo.isCBT && leftInfo.height==rightInfo.height) { isCBT=true; } } } return new Info(isFull, isCBT, height); } public static boolean isCBT2(Node head) { return process1(head).isCBT; } public static Node generateRandomBST(int maxLevel,int maxValue) { return generate(1, maxLevel, maxValue); } public static Node generate(int level,int maxLevel,int maxValue) { if(level>maxLevel || Math.random()<0.5) { return null; } Node head=new Node((int)(Math.random()*maxValue)); head.left=generate(level+1, maxLevel, maxValue); head.right=generate(level+1, maxLevel, maxValue); return head; } public static void main(String[] args) { int testTimes=1000000; int maxLevel=5; int maxValue=100; for(int i=0; i<testTimes; i++) { Node head=generateRandomBST(maxLevel, maxValue); if(isCBT1(head)!=isCBT2(head)) { System.out.println("oops"); } } System.out.println("finish"); } }
