298. Binary Tree Longest Consecutive Sequence - cocoder39/coco39_LC GitHub Wiki

298. Binary Tree Longest Consecutive Sequence

Main idea is simple, be careful that the base case is 1 consecutive number instead of 0

dfs, O(n) time and O(height) space

class Solution {
public:
    int longestConsecutive(TreeNode* root) {
        if (! root) {
            return 0;
        }
        
        int res = 1;
        helper(res, root, 1);
        return res;
    }
private:
    void helper(int& res, TreeNode* root, int cur) {
        if (root->left) {
            if (root->val + 1 == root->left->val) {
                res = max(res, cur + 1);
                helper(res, root->left, cur + 1);
            }
            else {
                helper(res, root->left, 1);
            }
        }
        
        if (root->right) {
            if (root->val + 1 == root->right->val) {
                res = max(res, cur + 1);
                helper(res, root->right, cur + 1);
            }
            else {
                helper(res, root->right, 1);
            }
        }
    }
};

follow up: return the one / all longest path(s)