判断一棵树是否是平衡二叉树

平衡二叉树定义：对于一棵树中任一节点，它的左子树和右子树的高度差不超过1（满二叉树一定是平衡二叉树，但平衡二叉树不一定是满二叉树）

套路：递归函数很好用，它不仅仅用来写先序中序后序，它还能解决很多问题，抛开先序后序中序这些个顺序来看，递归来到每个节点的顺序，它会回到每个节点三次，也就是说，我既然可以回到一个节点三次，我就可以想办法收集一下左子树上的信息，收集一下右子树的信息，然后把这些信息做整合来判断节点X所在的整棵树符不符合我们的标准。（拿本道题来说，就是判断看它符不符合平衡性的标准）

那么，为了实现判断一棵树是不是平衡二叉树，大的思路是如果以每个节点为头结点的树都是平衡二叉树，那么整棵树就是平衡二叉树。哪怕有任何一棵子树破坏了这个标准，那么整棵树就不平衡了。

考虑一个最基本的问题，假如遍历到某个节点X，怎么去判断X的整棵树是平衡的？要收集哪些信息：

1 判断左子树是否平衡，如果不平衡，直接返回false；

2判断右子树是否平衡，如果右子树不平衡，返回false；

3 在左子树和右子树都平衡的情况下，左子树的高度是？右子树的高度是？

4 然后就可以判断左子树和右子树的高度差是否超过1

然后就可以设计递归返回结构。因为我们整体是在一个递归函数里面去做判断的，所以左子树的过程应该给出一个返回值，这个返回值里面包括左子树是否平衡和左子树高度这两个信息。右子树的过程也给出一个返回值，包括右子树是否平衡和右子树高度这两个信息。返回值的结构类型应该是一样的。最后整理会发现我们的递归函数的返回值应该包含两个信息：第一这棵树是否是平衡的；第二这棵树的高度是什么。

package com.tree;

public class IsBalancedTree {

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

		public Node(int data) {
			this.value = data;
		}
	}

	public static boolean isBalance(Node head) {
		boolean[] res = new boolean[1];
		res[0] = true;
		getHeight(head, 1, res);
		return res[0];
	}

	public static int getHeight(Node head, int level, boolean[] res) {
		if (head == null) {
			return level;
		}
		int lH = getHeight(head.left, level + 1, res);
		if (!res[0]) {
			return level;
		}
		int rH = getHeight(head.right, level + 1, res);
		if (!res[0]) {
			return level;
		}
		if (Math.abs(lH - rH) > 1) {
			res[0] = false;
		}
		return Math.max(lH, rH);
	}
	

	public static void main(String[] args) {
		Node head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.left.right = new Node(5);
		head.right.left = new Node(6);
		head.right.right = new Node(7);

		System.out.println(isBalance(head));

	}

}

上面这种代码看不太懂，我比较能看懂下面这种

package com.tree;

public class isBalanceTree {
		public static class Node {
			public int value;
			public Node left;
			public Node right;
	
			public Node(int data) {
				this.value = data;
			}
		}
		
		public static class ReturnData{
			public boolean isB;
			public int h;
			
			public ReturnData(boolean isB,int h){
				this.isB = isB;
				this.h= h; 
			}
		}
		
		public boolean isB(Node head){
			return process(head).isB;
		}
		
		public static ReturnData process(Node head){
			if(head == null){
				return new ReturnData(true,0); //空树是平衡的
			}
			ReturnData leftData = process(head.left);
			if(!leftData.isB){
				return new ReturnData(false,0);
			}
			ReturnData rightData = process(head.right);
			if(!rightData.isB){
				return new ReturnData(false,0);
			}
			if(Math.abs(leftData.h-rightData.h)>1){
				return new ReturnData(false,0);
			}
			return new ReturnData(true,Math.max(leftData.h,rightData.h)+1);
		}
}