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.
题意：判断一个二叉树，是不是平衡二叉树。
思路：递归遍历一棵树判断子树的树高，如果相差不超过1，那么就是平衡二叉树。
java代码：
public static boolean isBalanced(TreeNode root) {
if (root == null)
return true;
int distance = getDeep(root.left) - getDeep(root.right);
if (distance > 1 || distance < -1)
return false;
else
return isBalanced(root.left) && isBalanced(root.right);
}
// 最大深度
public static int getDeep(TreeNode root) {
if (root == null)
return 0;
int level = 0;
LinkedList<TreeNode> list = new LinkedList<TreeNode>();
list.add(root);
int first = 0;
int last = 1;
while (first < list.size()) {
last = list.size();
while (first < last) {
if (list.get(first).left != null) {
list.add(list.get(first).left);
}
if (list.get(first).right != null) {
list.add(list.get(first).right);
}
first++;
}
level++;
}
return level;
}
