Balanced Binary Tree

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.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
     //两个递归，一个递归求树的高度，另一个递归求左右树是否平衡
    
     if (root == NULL)
     return true;
     int l= height(root->left);
     int r= height(root->right);
     if(l-r>=-1&&l-r<=1)
     return isBalanced(root->left)&&isBalanced(root->right);
     else
     return false;
    }
    int height (TreeNode* root)
    {
        if(root==NULL)
        return 0;
        else
        {if (root->left ==NULL )
         return  height(root->right)+1;
         if(root->right == NULL)
         return  height(root->left)+1;
         else
         {
             int l= height(root->left)+1;
             int r= height(root->right)+1;
             return max(l,r);
         }
           
        }
    }
   
   
};

Balanced Binary Tree

原文：http://www.cnblogs.com/gofighting/p/5036234.html