一、题目

        给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：

• 树上节点的数目在范围 [2, 1000] 内
• -231 <= Node.val <= 231 - 1

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？

二、解题思路

2.1 递归方法

        这道题目涉及二叉搜索树中两个节点被错误交换的情况。要解决这个问题，首先需要理解二叉搜索树的性质。二叉搜索树的定义是：如果左子树不为空，则左子树上所有节点的值都小于根节点的值；如果右子树不为空，则右子树上所有节点的值都大于根节点的值；同时，左子树和右子树本身也必须是二叉搜索树。

        二叉搜索树的一个重要特性是，其中序遍历的结果是一个有序的序列。基于这一点，我们可以通过中序遍历来检测问题。具体来说，如果在遍历过程中发现当前节点的值小于前一个节点的值，就说明出现了逆序，这意味着至少有一个节点被错误地放置了。我们只需要找到这两个错误的节点，然后将它们的值交换回来即可解决问题。

        通过这种方法，我们可以有效地定位并修复二叉搜索树中的错误节点。

#include <iostream>
using namespace std;// 定义二叉树节点
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};class Solution {
private:TreeNode* pre = nullptr;  // 当前节点的前一个节点TreeNode* first = nullptr;  // 第一个错误的节点TreeNode* second = nullptr;  // 第二个错误的节点public:void recoverTree(TreeNode* root) {// 递归中序遍历inorder(root);// 交换两个错误节点的值if (first && second) {swap(first->val, second->val);}}private:void inorder(TreeNode* root) {if (!root) return;// 遍历左子树inorder(root->left);// 检查是否出现逆序if (pre && pre->val > root->val) {if (!first) {first = pre;  // 第一个错误节点是 pre}second = root;  // 第二个错误节点是当前节点}pre = root;  // 更新 pre// 遍历右子树inorder(root->right);}
};// 打印二叉树的中序遍历结果（用于验证）
void printInorder(TreeNode* root) {if (!root) return;printInorder(root->left);cout << root->val << " ";printInorder(root->right);
}int main() {// 构建一个错误的二叉搜索树TreeNode* root = new TreeNode(3);root->left = new TreeNode(1);root->right = new TreeNode(4);root->right->left = new TreeNode(2);cout << "原始树的中序遍历: ";printInorder(root);cout << endl;// 修复二叉搜索树Solution solution;solution.recoverTree(root);cout << "修复后的中序遍历: ";printInorder(root);cout << endl;return 0;
}

2.2 非递归方法

#include <iostream>
#include <stack>
using namespace std;// 定义二叉树节点
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};class Solution {
public:void recoverTree(TreeNode* root) {stack<TreeNode*> stack;  // 存储节点的栈TreeNode* pre = nullptr;  // 当前节点的前一个节点TreeNode* first = nullptr;  // 第一个错误的节点TreeNode* second = nullptr;  // 第二个错误的节点while (root || !stack.empty()) {// 遍历左子树while (root) {stack.push(root);root = root->left;}// 访问当前节点if (!stack.empty()) {root = stack.top();stack.pop();// 检查是否出现逆序if (first == nullptr && pre != nullptr && pre->val > root->val) {first = pre;  // 第一个错误节点是 pre}if (first != nullptr && pre->val > root->val) {second = root;  // 第二个错误节点是当前节点}pre = root;  // 更新 pre// 遍历右子树root = root->right;}}// 交换两个错误节点的值if (first && second) {swap(first->val, second->val);}}
};// 打印二叉树的中序遍历结果（用于验证）
void printInorder(TreeNode* root) {if (!root) return;printInorder(root->left);cout << root->val << " ";printInorder(root->right);
}int main() {// 构建一个错误的二叉搜索树TreeNode* root = new TreeNode(3);root->left = new TreeNode(1);root->right = new TreeNode(4);root->right->left = new TreeNode(2);cout << "原始树的中序遍历: ";printInorder(root);cout << endl;// 修复二叉搜索树Solution solution;solution.recoverTree(root);cout << "修复后的中序遍历: ";printInorder(root);cout << endl;return 0;
}