C++ Non-recursive, Non-stack/queue solution, based on Morris Traversal


  • 0
    A

    I bet that Morris must have hated recursive, me too.
    Why did Morris devise this traversal method? I bet it is because Morris didn't want to be treated as trivial in interview.

    class Solution {
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<vector<int>> vv;
            vector<int> v;
            TreeNode *p, *t = root;
            int m = 0;
            while (t) {
                m += t->val;
                v.push_back(t->val);
                if (p = t->left) {
                    int d = 1, n = p->val;
                    v.push_back(p->val);
                    while (p->right && p->right != t) {
                        p = p->right;
                        v.push_back(p->val);
                        n += p->val;
                        d++;
                    }
                    if (p->right) {
                        p->right = NULL;
                        m -= t->val + n;
                        v.erase(v.end()-2*d-1, v.end());
                        t = t->right;
                    } else {
                        p->right = t;
                        if (!p->left && m + n == sum) vv.push_back(v);
                        v.erase(v.end()-d, v.end());
                        t = t->left;
                    }
                } else {
                    t = t->right;
                    if (!t && m == sum) vv.push_back(v); 
                }
            }
            return vv;
        }
    };
    

Log in to reply
 

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