O(N), C++, simple, recursive solution


  • 0
    C
    class Solution {
    public:
        int dfs(TreeNode *root, int &max_len)
        {
            if (!root) return 0;
            
            int left_len = 0;
            int right_len = 0;
            
            left_len = dfs(root->left, max_len);
            right_len = dfs(root->right, max_len);
            
            int curr_len = 1;
            int consecutive = 0;
            if (root->left && root->left->val - 1 == root->val)
                left_len++, consecutive = 1;
            if (root->right && root->right->val - 1 == root->val)            
                right_len++, consecutive = 1;
            
            int max_curr = max(left_len, right_len);
            curr_len = consecutive ? max_curr: 1;
            max_len = max(max_len, max(max_curr, curr_len));
            return curr_len;
        }
        int longestConsecutive(TreeNode* root) {
            int max_len = 0;
            dfs(root, max_len);
            return max_len;
        }    
    };

Log in to reply
 

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