C++ O(n) time beats 100% Solution WITH explanation


  • 0
    U

    Basic idea:

    • Take one traverse of the tree
    • Maintain nodes contain max&min value bottom-up
    • If left subtree's max value > current->val, keep the left subtree's max node as value.second
    • If right subtree's min value < current->val, keep the right subtree's min node as value.first
    • If only value.first or value.second is updated, set the other one to be current
    • After the traversal, swap value.first->val and value.second->val will simply do the job since after the last time value is updated it contains the two swapped nodes.
    class Solution {
    public:
        pair<TreeNode*, TreeNode*>& checkAndSet(TreeNode* current, pair<TreeNode*, TreeNode*>& value) {
            TreeNode* min = current;
            TreeNode* max = current;
            pair<TreeNode*, TreeNode*> tmpValue(current, current);
            int flag = 0;
            if (!current->left && !current->right) {
                pair<TreeNode*, TreeNode*> ans(min, max);
                return ans;
            }
            if (current->left) {
                pair<TreeNode*, TreeNode*> tmp = checkAndSet(current->left, value);
                if (tmp.second->val > current->val) {
                    tmpValue.second = tmp.second;
                    flag = 1;
                }
                if (tmp.first->val < min->val)
                    min = tmp.first;
                if (tmp.second->val > max->val)
                    max = tmp.second;
            }
            if (current->right) {
                pair<TreeNode*, TreeNode*> tmp = checkAndSet(current->right, value);
                if (tmp.first->val < current->val) {
                    tmpValue.first = tmp.first;
                    flag = 1;
                }
                if (tmp.first->val < min->val)
                    min = tmp.first;
                if (tmp.second->val > max->val)
                    max = tmp.second;
            }
            if (flag)
                value = tmpValue;
            pair<TreeNode*, TreeNode*> ans(min, max);
            return ans;
        }
        
        void recoverTree(TreeNode* root) {
            pair<TreeNode*, TreeNode*> value(NULL, NULL);
            checkAndSet(root, value);
            int tmp = value.first->val;
            value.first->val = value.second->val;
            value.second->val = tmp;
        }
    };
    

Log in to reply
 

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