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

代码实现

/**
 * 平衡二叉树：对于任何一棵子树来说，它的左子树和右子树的高度差不超过1。
 * 即左子树需要是平衡二叉树，右子树是平衡二叉树，左子树与右子树的高度差小于等于1.
 * 需要的信息：左树是否是平衡二叉树，左树的高度；右树是否是平衡二叉树，右树的高度
 * @author zyt
 *
 */
public class IsBalancedTree {
	
	/**
	 * 手动定义一个二叉树
	 * @author 12068
	 *
	 */
	public static class Node{
		public int value;
		public Node left;
		public Node right;
		
		public Node(int data){
			this.value = data;
		}
	}
	
	/**
	 * 判断是否是平衡二叉树
	 * @param head 头节点
	 * @return
	 */
	public static boolean isBalanced(Node head){
		return process(head).isBalanced;
	}
	

	//由于需要的子树的信息包含两部分，所以定义一个返回值的类型
	public static class ReturnType{
		public boolean isBalanced;//是否是平衡二叉树
		public int height;//平衡二叉树的高度
		
		public ReturnType(boolean isB, int hei){
			isBalanced = isB;
			height = hei;
		}
	}
	
	
	public static ReturnType process(Node x) {
		//如果是空树，则也是平衡二叉树
		if(x == null){
			return new ReturnType(true, 0);
		}
		//从左树获取的信息
		ReturnType leftData = process(x.left);
		//从右树获取的信息
		ReturnType rightData = process(x.right);
		
		//以x为头节点的树的高度
		int hegiht = Math.max(leftData.height, rightData.height) + 1;
		//以x为头节点的树是否是平衡二叉树:
		//左子树需要是平衡二叉树，右子树是平衡二叉树，左子树与右子树的高度差小于等于1
		boolean isBalanced = leftData.isBalanced && rightData.isBalanced 
				&& Math.abs(leftData.height - rightData.height) < 2;
		return new ReturnType(isBalanced, hegiht);
	}
}