C++ Solution ...O(n) time complexity


  • 0
    T
    int longestConsecutive(TreeNode* root) {
        if(root == nullptr)
            return 0;
        
        int max = 1;
        int current = 1;
        longestConsecutive_impl(root, current, max);
        
        return max;
    }
    
    void longestConsecutive_impl(TreeNode* root, int& current, int& max) {
        if(root == nullptr){
            return;
        }
        
        int left_current = 0, right_current = 0;
        longestConsecutive_impl(root->left, left_current, max);
        longestConsecutive_impl(root->right, right_current, max);
            
        if (root->left && (root->left->val - root->val == 1))
            ++left_current;
        else
            left_current = 1;
            
        if (root->right && (root->right->val - root->val == 1))
            ++right_current;
        else
            right_current = 1;
        
        current = std::max(left_current, right_current);
        max = std::max(max, current);
    }

Log in to reply
 

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