二叉樹的遞回套路——完全二叉樹

給定一棵二叉樹的頭節點head,回傳這顆二叉樹中是不是完全二叉樹

什么是完全二叉樹，一句話可以總結——這棵樹的每一層，要么就是滿的，要么就是從左到右依次變滿的，

方法一

（網上最常見的，不用二叉樹的遞回套路）：寬度優先遍歷這棵樹，如有不了解寬度優先遍歷的，可以看看這篇文章——二叉樹的按層遍歷，在寬度優先遍歷二叉樹的時候，做如下判斷：

• 遇到的每一個結點，如果有右孩子，但是沒有左孩子，一定不是完全二叉樹，因為一定是要從左到右依次變滿的，
• 一旦遇到第一個左右孩子不雙全的結點，接下來遇到的所有結點，都必須是葉子結點， 這種情況下，一定是完全二叉樹，

給大伙畫棵樹，大家自己對著上面兩個條件判斷一下，

方法二

二叉樹的遞回套路，二叉樹的遞回套路威力是無窮的，關鍵在于列可能性，判斷一棵樹是否為完全二叉樹，我們以最后一層的最后一個結點到哪了進行分類，

1）無缺口：所有層都是滿的，沒有缺口位置（缺口就是最后一層成長到的位置，）這種情況下這棵樹就是滿二叉樹，

此時，我們需要向左樹要的資訊是：（假設以X為頭節點，下文也是）左樹整體是否是滿二叉樹+左樹的高度， 右樹也一樣，如果左右都是滿二叉樹的并且高度一樣，那么以X為頭節點的整顆樹就是滿二叉樹，

2）有缺口：又有三種可能

1》：缺口停留在左樹的位置，沒有越過左樹邊界到右樹上去，

滿足這種情況需要的條件是：
左樹整體是完全二叉樹
&&
右樹整體是滿二叉樹
&&
左樹高度==右樹高度+1

2》：左樹成長情況是左樹已經撐滿了，右樹全為空，
左樹是滿二叉樹 && 右樹是滿二叉樹 && 左樹高度==右樹高度+1

3》：最后一層成長的位置把左樹撐滿了，并且來到了右樹上，
左樹是滿二叉樹 && 右樹是完全二叉樹 && 左右高度一樣

以上將所有可能性全部列了出來，如果四種情況都不成立，則必定不是完全二叉樹，如果四個中有一個成立就是完全二叉樹，

接下來進行整合，向每顆子樹要的資訊就是如下三個：

1. 整顆子樹是否是滿二叉樹
2. 整顆子樹是否是完全二叉樹
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");
	}
}