[leetcode] 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.

给一棵二叉树，判断其是否为平衡二叉树。

使用递归，如果一棵树是平衡二叉树，那么他的左子树和右子树也应该是平衡二叉树，而且两子树的高度差不超过1。depth为该节点的深度初始化为0。

代码如下：

/** 
 * Definition for binary tree 
 * struct TreeNode { 
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
 * }; 
 */ 
class Solution {  
    public:  
        bool isBalanced(TreeNode *root) {  
            // Note: The Solution object is instantiated only once and is reused by each test case.  
            int depth = 0;  
            return isbalance(root, depth);  
        }  
        bool isbalance(TreeNode *root, int &depth)  
        {  
            if(root == NULL)  
            {  
                depth = 0;  
                return true;  
            }  
            int ld,rd;  
            if( isbalance(root->left,ld) && isbalance(root->right,rd))  
            {  
                if( abs(ld - rd) > 1)  
                {  
                    return false;  
                }  
                depth = ld > rd ? ld + 1 : rd + 1;  
                return true;  
            }
            else return false;
        }  
};