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

• 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;
}
};

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