My C++ O(1) space in order traval


  • -2
    L

    Simple in order travel, use constant space to keep track of some recent visited nodes.
    At each step, check if the order is correct, if it isn't then there's something wrong, record it.
    Finally check these suspicious situation and find the swapped values;

    class Solution {
    public:
        int a, b, c;
        TreeNode * x, * y, * z;
        vector<TreeNode *> swaps;
        
        void check_for_swap()
        {
            if (y && z)
                if (b > c)
                {
                    // the order here is not correct, take a note
                    swaps.push_back(y);
                    swaps.push_back(z);
                }
        }
        
        // in order travel
        void travel(TreeNode * n)
        {
            // go left
            if (n->left)
                travel(n->left);
            
            // visit
            // update recent values
            a = b;
            b = c;
            c = n->val;
            
            x = y;
            y = z;
            z = n;
            
            check_for_swap();
            
            // go right
            if (n->right)
                travel(n->right);
        }
        
        void recoverTree(TreeNode *root) {
            
            a = -1;
            b = -1;
            c = -1;
            x = NULL;
            y = NULL;
            z = NULL;
            
            travel(root);
            
            // if the swaped elements are adjacent, then swaps.size() == 2
            // else swaps.size() == 4, the swaped nodes are the 1st and the last one, so:
            if (swaps.size() == 4)
            {
                swaps.erase(swaps.begin() + 1);
                swaps.erase(swaps.begin() + 1);
            }
            if (swaps.size() == 2)
            {
                int v = swaps[0]->val;
                swaps[0]->val = swaps[1]->val;
                swaps[1]->val = v;
            }
        }
    };

  • 2
    L

Log in to reply
 

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