12ms, C++, O(n) solution


  • 0
    Y
    /**
     * 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 = isBalanced_help(root->left);
            int r = isBalanced_help(root->right);
            if(l < 0 || r < 0){
                return false;
            }else{
                return (l < r ? (r - l) : (l - r) ) <= 1;
            }
        }
        
        int isBalanced_help(TreeNode* root){
            // if balanced return the deepest height between left and right, otherwise return -1
            if(root == NULL) return 0;
            int l = isBalanced_help(root->left);
            int r = isBalanced_help(root->right);
            if(l < 0 || r < 0){
                return -1;
            }else{
                if((l < r ? (r - l) : (l - r) ) <= 1){
                    return l < r ? r + 1 : l + 1;
                }else{
                    return -1;
                }
            }
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.