C++ Non-recursive O(1) space, *NOT* Morris Traversal


  • 0
    A

    Well, I reckon I used kind of a hack, but it should work on almost all systems.
    More importantly, this is non-recursive O(1) space but NOT Morris Traversal.
    You can't find a similar one like this in any other post. This one is unique.
    Other non-recursive O(1) space traversals in other posts are all based on Morris.

    class Solution {
    public:
        vector<int> inorderTraversal(TreeNode* root) {
            vector<int> v;
            TreeNode *t, *p = root, *c = p ? p->left : NULL;
            for (bool d = true, f = false; p; ) {
                if (d && c) {
                    if (!c->left && !c->right) {
                        v.push_back(c->val);
                        d = false;
                    } else {
                        t = p;
                        p = c;
                        c = c->left;
                        p->left = (TreeNode*)~(uintptr_t)t;
                        f = false;
                    }
                } else if (!f && ((d && !p->left) || (!d && p->left == c) || p->left > p->right)) {
                        v.push_back(p->val);
                        t = c;
                        c = p->right;
                        if (p->left != t) p->right = p->left;
                        p->left = t;
                        d = c ? true : false;
                        f = true;
                } else {
                        if (p == root) break;
                        t = c;
                        c = p;
                        p = (TreeNode*)~(uintptr_t)p->right;
                        c->right = t;
                        d = false;
                        f = false;
                }
            }
            return v;
        }
    };
    

Log in to reply
 

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