[C++] Clean Code - 2 Solution - return vector or struct


  • 1

    Return vector

    class Solution {
    public:
        int longestConsecutive(TreeNode* root) {
            int maxlen = 0;
            dfs(root, maxlen);
            return maxlen;
        }
    
    private:
        vector<int> dfs(TreeNode* node, int& maxlen) {
            if (!node) {
                return {0,0};
            }
    
            vector<int> p(2, 1);
            int l2r = 1;
            int r2l = 1;
    
            if (node->left) {
                vector<int> l = dfs(node->left, maxlen);
                int lv = node->left->val;
                if (node->val + 1 == lv) {
                    p[0] = max(p[0], 1 + l[0]);
                    r2l += l[0];
                }
                if (node->val - 1 == lv) {
                    p[1] = max(p[1], 1 + l[1]);
                    l2r += l[1];
                }
            }
    
            if (node->right) {
                vector<int> r = dfs(node->right, maxlen);
                int rv = node->right->val;
                if (node->val + 1 == rv) {
                    p[0] = max(p[0], 1 + r[0]);
                    l2r += r[0];
                }
                if (node->val - 1 == rv) {
                    p[1] = max(p[1], 1 + r[1]);
                    r2l += r[1];
                }
            }
            maxlen = max(maxlen, max(max(l2r, r2l), max(p[0], p[1])));
            return p;
        }
    };
    

    Return Struct

    class Solution {
    public:
        int longestConsecutive(TreeNode* root) {
            int maxlen = 0;
            dfs(root, maxlen);
            return maxlen;
        }
    
    private:
        struct RetnInfo {
            int inc;
            int desc;
            RetnInfo(int inc, int desc) : inc(inc), desc(desc) {};
        };
    
        RetnInfo dfs(TreeNode* node, int& maxlen) {
            if (!node) {
                return RetnInfo(0, 0);
            }
    
            RetnInfo p(1, 1);   // return info for parent
            int lr = 1, rl = 1; // lr - left to right; rl - right to left;
            RetnInfo l = dfs(node->left, maxlen);
            RetnInfo r = dfs(node->right, maxlen);
    
            if (node->left && node->left->val == node->val + 1) {
                p.inc = max(p.inc, 1 + l.inc);
                rl += l.inc;
            }
            if (node->left && node->left->val == node->val - 1) {
                p.desc = max(p.desc, 1 + l.desc);
                lr += l.desc;
            }
    
            if (node->right && node->right->val == node->val + 1) {
                p.inc = max(p.inc, 1 + r.inc);
                lr += r.inc;
            }
            if (node->right && node->right->val == node->val - 1) {
                p.desc = max(p.desc, 1 + r.desc);
                rl += r.desc;
            }
    
            maxlen = max(maxlen, max(max(lr, rl), max(p.inc, p.desc)));
            return p;
        }
    };
    

Log in to reply
 

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