平衡二叉树

题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。

分析
首先我们要知道AVL树性质，不了解的可以看这篇文章：平衡二叉树(AVL)的理解和实现(Java)

我们知道平衡二叉树是高度平衡化的二叉搜索树，那么对于任意一个节点，其左右子树的高度差不大于1，如果存在某个节点左右子树深度差大于1，那么一定不是AVL树。

节点类：

public class TreeNode {
	int val = 0;
	TreeNode left = null;
	TreeNode right = null;

	public TreeNode(int val) {
		this.val = val;
	}
}

方法一

	/**
	 * 方法一
	 * @param root
	 * @return
	 */
	public boolean IsBalanced_Solution(TreeNode root) {
		if(root == null) {
			return true;
		}
		return Math.abs(depth(root.left) - depth(root.right)) <= 1 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
	}

	private int depth(TreeNode node) {
		if(node == null) return 0;

		int m = depth(node.left);
		int n = depth(node.right);

		return m > n ? m + 1 : n + 1;
	}

这是最直接的做法，遍历每个结点，借助一个获取树深度的递归函数，根据该结点的左右子树高度差判断是否平衡，然后递归地对左右子树进行判断。

但是我们发现该方法在判断上层结点的时候，会多次重复遍历下层结点，增加了不必要的开销。如果改为从下往上遍历，如果子树是平衡二叉树，则返回子树的高度；如果发现子树不是平衡二叉树，则直接停止遍历，这样至多只对每个结点访问一次。

方法二

	/**
	 * 方法二
	 * @param root
	 * @return
	 */
	public boolean isAVL = true;
	
	public boolean IsBalanced_Solution_2(TreeNode root) {
		getdepth(root);
		return isAVL;
	}
	
	private int getdepth(TreeNode node) {
		if(!isAVL) return 0;
		if(node == null) return 0;
		int m = getdepth(node.left);
		int n = getdepth(node.right);
		if(Math.abs(m - n) > 1) {
			isAVL=false;
		}

		return m > n ? m + 1 : n + 1;
	}