[leetcode]Balanced Binary Tree

新博文地址：[leetcode]Balanced Binary Tree

 

http://oj.leetcode.com/problems/balanced-binary-tree/

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

 判断是否是平衡二叉树

百科 

又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

 偷懒用了递归算法，没什么难度

    public boolean isBalanced(TreeNode root) {
		if (root == null) {
			return true;
		}
		int left = getHeight(root.left);
		int right = getHeight(root.right);
		if (Math.abs(left - right) > 1) {
			return false;
		}
		if (root.left != null && !isBalanced(root.left)) {
			return false;
		}
		if (root.right != null && !isBalanced(root.right)) {
			return false;
		}
		return true;
    }
	  private int getHeight(TreeNode root) {
		if (root == null) {
			return 0;
		}
		if (root.left == null && root.right == null) {
			return 1;
		}
		int leftHeight = getHeight(root.left);
		int rightHeight = getHeight(root.right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}