二叉树的递归套路——满二叉树

二叉树的递归套路——满二叉树 给定一棵二叉树的头节点head，返回这颗二叉树是不是满二叉树

特点：如果一颗二叉树的有L层，结点个数是N个的话，必定满足以下这个公式：
(2^L)-1 == N，且只有满二叉树有这个特点

根据二叉树的递归套路，以及满二叉树的特点，我们向每颗子树要的信息就是高度和结点个数。比较简单，就不赘述了。直接看代码叭：

package com.harrison.class08;

public class Code05_IsFull {
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}
	
	public static class Info{
		public int height;
		public int nodes;
		
		public Info(int h,int n) {
			height=h;
			nodes=n;
		}
	}
	
	public static Info process1(Node head) {
		if(head==null) {
			return new Info(0, 0);
		}
		Info leftInfo=process1(head.left);
		Info righInfo=process1(head.right);
		int height=Math.max(leftInfo.height, righInfo.height)+1;
		int nodes=leftInfo.nodes+righInfo.nodes+1;
		return new Info(height, nodes);
	}
	
	public static boolean isFull1(Node head) {
		if(head==null) {
			return true;
		}
		Info allInfo=process1(head);
		return (1< 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 maxLevel = 5;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
			Node head = generateRandomBST(maxLevel, maxValue);
			if (isFull1(head) != isFull2(head)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}
}