Sunday, April 21, 2013

Leetcode: Balanced Binary Tree in C++


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 ofevery node never differ by more than 1.

Solution: 
int GetHeight(TreeNode *root)
    {
        if(!root)
        return 0;
        int leftheight = GetHeight(root->left);
        int rightheight = GetHeight(root->right);
        if(leftheight-rightheight>1||leftheight-rightheight<-1||rightheight ==-1||leftheight ==-1)
        return -1;
        return leftheight>rightheight?leftheight+1:rightheight+1;
        
    }
    bool isBalanced(TreeNode *root) {
        if(!root)
        return true;
        int result = GetHeight(root);
        if(result==-1)
        return false;
        else 
        return true;
    }

No comments:

Post a Comment