class Solution2 { public: TreeNode* n1 = nullptr, *n2 = nullptr; voidrecoverTree(TreeNode *root){ if (!root) return;

TreeNode* prev = nullptr, *cur = nullptr; while (root) { if (!root->left) { prev = cur; cur = root; root = root->right; } else { auto* l = root->left; while (l->right && l->right != root) l = l->right; if (l->right == root) { prev = cur; cur = root; root = root->right; l->right = nullptr; } else { l->right = root; root = root->left; } } if (prev && prev->val > cur->val) { if (!n1) { n1 = prev; n2 = cur; } else { n2 = cur; } } }

std::swap(n1->val, n2->val); } };

PS: I found there is also a solution that first cleverly transforms the tree into an ordered linked-list and then detects the misplaced elements and then restore it back.