REAL O(1) Space (No recursion/No stack, etc) O(n) Time solution. 48ms C++


  • 10
    F

    Someone complained that a recursion solution isn't really a O(1) space solution. Ok, here comes the real O(1) solution. No recursion, no stack. Pure Morris traversal. 48 ms, C++ :

    class Solution {
            TreeNode * wrong_node0 = nullptr, * wrong_node1 = nullptr, * prev = nullptr;
            void verify(TreeNode * cur)
            {
                if (prev != nullptr && prev -> val > cur -> val)
                {
                    if (wrong_node0 == nullptr)
                    {
                        wrong_node0 = prev;
                        wrong_node1 = cur; // in case the tree has only 2 elements.
                    }
                    else
                        wrong_node1 = cur;
                }
                prev = cur;
            }
            void morrisInorder(TreeNode * root)
            {
                TreeNode * cur = root;
                while (cur)
                {
                    if (cur->left == nullptr)
                    {
                        verify(cur);       
                        cur = cur->right;
                        continue;
                    }
                    TreeNode * pred = cur->left;
                    while (pred -> right != nullptr && pred -> right != cur)
                        pred = pred -> right; //finding predecessor
                    if (pred -> right == nullptr)
                    {
                        pred -> right = cur;
                        cur = cur -> left;
                    }else {//pred -> right == cur;
                        pred -> right = nullptr;
                        verify(cur);
                        cur = cur -> right;
                    }
                }
            }
        public:
            void recoverTree(TreeNode* root) {
                morrisInorder(root);
                swap(wrong_node0->val, wrong_node1->val);
            }
        };

  • 0
    R

    where are the explanation then?


  • 0
    F

    First of all, the title doesn't say "with explanation". So it is legitimate to not post the expiation.
    Second, it also says it is using Morris Traversal. I think this explains everything.


  • 0
    P

    Previously it is not ok to post solutions without any explanation. Quote:
    closed with the note: Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the [Discuss FAQ](http://oj.leetcode.com/discuss/faq) for more info. Take a look at [good sharing example](https://oj.leetcode.com/discuss/8092/my-dp-o-n-solution-without-using-stack) See.https://leetcode.com/discuss/10283/my-solution-in-c-dfs But now no one cares.


  • 1
    F

    I also said, it was "Pure Morris traversal". I think this is explanatory enough. I don't think people who thought about this question don't understand it.


  • 0
    T

    What kind of name "fentoyal" is...


  • 1
    F

    What kind of question "What kind of name "fentoyal" is..." is??


Log in to reply
 

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