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 public class Solution { 2 private int height(TreeNode root){ 3 if(root == null) 4 return 0; 5 int left = height(root.left); 6 int right = height(root.right); 7 8 return Math.max(left, right)+1; 9 } 10 public boolean isBalanced(TreeNode root) { 11 if(root == null) 12 return true; 13 int left = height(root.left); 14 int right = height(root.right); 15 16 if(Math.abs(left-right)>1) 17 return false; 18 return isBalanced(root.left) & isBalanced(root.right); 19 } 20 }
这种方法耗时428ms。
第二种方法在递归求树的高度的过程中顺便判断树是否平衡，如果在某个节点处，该节点的左子树和右子树高度只差大于1，或者该树的左子树或者又子树不平衡，那么返回该树的高度为-1；否则返回该树的高度。
代码如下：
1 public class Solution { 2 private int height(TreeNode root){ 3 if(root == null) 4 return 0; 5 int left = height(root.left); 6 int right = height(root.right); 7 8 if(left == -1 || right == -1 || Math.abs(left - right) > 1) 9 return -1; 10 return Math.max(left, right)+1; 11 } 12 public boolean isBalanced(TreeNode root) { 13 return height(root) != -1; 14 } 15 }
这种方法耗时464ms。
【leetcode】Balanced Binary Tree,布布扣,bubuko.com
【leetcode】Balanced Binary Tree
原文：http://www.cnblogs.com/sunshineatnoon/p/3851852.html