C++ solution - in-order traversal to pick up reversed nodes


  • 0
    I

    Here is my solution. I've added my own comment. Basically, there can be two cases.
    Two node have been reversed following in-order traversal or two distant nodes are swapped. We don't know which one is which so when we first find one reversed case, just store prev and cur and if we find another case later, store the current. Once we are done, swap what we collected.

    // do an in-order traversal and carry along pointer to previous node
    // if prev is greater than current, we've found reversal case
    // save that prev location for first and current one for second
    // if we later found additional node, set that to second
    // once we are done, swap the first and the second
    void traverse(TreeNode* root, TreeNode* &prev, TreeNode* &first, TreeNode* &second) {
        if (!root) return;
        traverse(root->left, prev, first, second);
        // found that the order is reversed
        if (prev && prev->val > root->val) {
            if (first) second = root;
            else  {first = prev; second = root;}
        }
        prev = root;
        traverse(root->right, prev, first, second);
    }
    void recoverTree(TreeNode* root) {
        TreeNode *first = nullptr, *prev = nullptr, *second = nullptr;
        traverse(root, prev, first, second);
        // swap
        if (first && second) {
            int tmp = first->val;
            first->val = second->val;
            second->val = tmp;
        }
    }

Log in to reply
 

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