Monday, November 25, 2013

LeetCode Problem : Balanced Binary Tree

Problem


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.

Code

int isb(TreeNode *root,bool& ok) {
    if(!ok)
        return 0;
    if(!root)
        return 0;
    int rd = isb(root->right,ok);
    int ld = isb(root->left,ok);
    if(abs(rd - ld) > 1){
        ok = false;
        return 0;
    }
    return (1 + max(rd , ld));
}

bool isBalanced(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
    if(!root)
        return true;
    bool ok = true;
    isb(root,ok);
    return ok;
}

No comments:

Post a Comment