Nobody's C++ solution


  • 0
    0

    not fast, but it is easy to finish with bugfree even on interview and good time complexsity

    class Solution {
    public:
        int longestConsecutive(TreeNode* root) {
            if (!root) return 0;
            unordered_map<TreeNode*, vector<TreeNode*>> g;
            queue<TreeNode*> q;
            q.push(root);
            while (!q.empty()) {
                TreeNode* t = q.front();
                q.pop();
                if (t->left) { g[t].push_back(t->left); g[t->left].push_back(t); q.push(t->left); }
                if (t->right) { g[t].push_back(t->right); g[t->right].push_back(t); q.push(t->right); }
            }
            int result = 0;
            for (auto& p : g) {
                result = max(result, helper(p.first, g));
            }
            return result + 1;
    
        }
        int helper(TreeNode* s, unordered_map<TreeNode*, vector<TreeNode*>>& g) {
            int level = 0;
            for (TreeNode* n : g[s]) {
                if (n->val == s->val + 1) level = max(level, 1 + helper(n, g));
            }
            return level;
        }
    };

Log in to reply
 

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