C++ Non-recursive O(1) space solution, based on Morris Traversal


  • 1
    A

    Yes, Morris again. Praise Morris.
    Traverse the tree only once with constant space.
    No nasty global variables, and not really using the previous-first-second method.

    class Solution {
    public:
        void recoverTree(TreeNode* root) {
            TreeNode *s[3][2], *p, *h = root;
            int v, n = 0;
            bool f = false;
            while (h) {
                if (p = h->left) {
                    while (p->right && p->right != h) p = p->right;
                    if (p->right) {
                        s[n][1] = h;
                        if (h->val < v) n++;
                        s[n][0] = h;
                        v = h->val;
                        h = h->right;
                        p->right = NULL;
                    } else {
                        p->right = h;
                        h = h->left;
                    }
                } else {
                    s[n][1] = h;
                    if (f && h->val < v) n++;
                    s[n][0] = h;
                    v = h->val;
                    h = h->right;
                    f = true;
                }
            }
            if (n==2) swap(s[0][0]->val, s[1][1]->val);
            else swap(s[0][0]->val, s[0][1]->val);
        }
    };
    

  • 0
    K

    Your's are really really O(1) space, some others said there recursive are O(1), but I think it is O(depth of tree), function calling stack should also be called SPACE.


Log in to reply
 

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