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.

---

解题思路：

递归地计算每个节点的左右子树深度，看其是否平衡。

计算左右子树深度可参考Maximum Depth of Binary Tree 的递归解法。

---

 Java code:

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public boolean isBalanced(TreeNode root) {        if(root == null) {            return true;        }        int diff = maxDepth(root.left) - maxDepth(root.right);        if(diff > 1 || diff < -1 ) {            return false;        }        return isBalanced(root.left) && isBalanced(root.right);    }        public int maxDepth(TreeNode root) {        //use recursion        if(root == null) {            return 0;        }        int leftmax = maxDepth(root.left);        int rightmax = maxDepth(root.right);        return Math.max(leftmax, rightmax) + 1;       }}

---

20160607  time complexity: O(nlgn)

public class Solution {    public boolean isBalanced(TreeNode root) {        //time complexity: O(nlgn)        //base case        if (root == null) {            return true;        }                int leftHeight = getHeight(root.left);        int rightHeight = getHeight(root.right);        if (Math.abs(leftHeight - rightHeight) > 1) {            return false;        }        return isBalanced(root.left) && isBalanced(root.right);    }        private int getHeight(TreeNode root) {  //time complexity: O(n)        if (root == null) {            return 0;        }        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;    }}

 

Reference:

1. http://www.cnblogs.com/infinityu/archive/2013/05/11/3073411.html