C++ recursive & iterative 13m


  • 0
    L

    recursive & iterative solution with same idea:

    int longestConsecutive(TreeNode* root) {
            if(!root) return 0;
            unordered_map<TreeNode*, pair<int,int>> map;
            stack<TreeNode*> stk;
            stk.push(root);
            int res = 0;
            while(stk.size()){
                TreeNode* cur = stk.top();
                if(cur -> left && map.count(cur -> left) == 0){
                    stk.push(cur -> left);
                    map[cur -> left] = {0, 0};
                }else if(cur -> right && map.count(cur -> right) == 0){
                    stk.push(cur -> right);
                    map[cur -> right] ={0, 0};
                }else{
                    stk.pop();
                    int asc = cur -> left && cur -> left -> val + 1 == cur -> val? map[cur -> left].first + 1 : 1;
                    asc = max(asc, cur -> right && cur -> right -> val + 1 == cur -> val? map[cur -> right].first + 1 : 1);
                    int dsc = cur -> left && cur -> left -> val - 1 == cur -> val? map[cur -> left].second + 1 : 1;
                    dsc = max(dsc, cur -> right && cur -> right -> val - 1 == cur -> val? map[cur -> right].second + 1 : 1);
                    res = max(res, asc + dsc - 1);
                    map[cur] = {asc, dsc};
                }
            }
            return res;
        }
    
    int longestConsecutive(TreeNode* root) {
            int res = 0;
            helper(root, &res);
            return res;
        }
        pair<int, int> helper(TreeNode* root, int* res){
            if(!root) return make_pair(0, 0);
            auto left = helper(root -> left, res);
            auto right = helper(root -> right, res);
            int ascend = root -> left && root -> left -> val + 1 == root -> val ? left.first + 1 : 1;
            ascend = max(ascend, root -> right && root -> right -> val + 1 == root -> val ? right.first + 1 : 1);
            int descend = root -> left && root -> left -> val - 1 == root -> val ? left.second + 1 : 1;
            descend = max(descend, root -> right && root -> right -> val - 1 == root -> val ? right.second + 1 : 1);
            *res = max(*res, ascend + descend - 1);
            return make_pair(ascend, descend);
        }
    

Log in to reply
 

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