LC.99 ｜ 恢复二叉搜索树 ｜ 树 ｜ 中序遍历找“逆序对”（定位两节点再交换）
输入：二叉搜索树根节点root，其中恰好有两个节点的值被错误交换。
要求：在不改变树结构的情况下恢复 BST（只允许改节点值）。
输出：无（原地修改root）。
思路：
BST 的中序遍历应该是严格递增序列。
一旦有两个节点值被交换，中序序列里就会出现“乱序”，表现为逆序对：
- 正常：
... a < b < c < d ... - 交换后可能出现：
- 相邻交换：只出现1 次逆序（例如
... a < c < b < d ...，在c > b处逆序） - 不相邻交换：出现2 次逆序（例如
... a < d < c < b ...，会在d > c、c > b两处逆序）
- 相邻交换：只出现1 次逆序（例如
所以我们中序遍历时维护prev（上一个访问的节点）：
- 若发现
prev->val > node->val，说明出现逆序。 - 第一次逆序：
first = prev（大的那个） - 每次逆序都更新
second = node（小的那个）- 相邻交换：只会更新一次
second - 不相邻交换：第二次逆序会把
second更新成最终正确的小节点
- 相邻交换：只会更新一次
遍历结束后交换first和second的值即可恢复。
复杂度：
- 时间复杂度：O(N)
- 空间复杂度：O(H)（递归栈，H 为树高）
classSolution{public:voidrecoverTree(TreeNode*root){first=nullptr;second=nullptr;prev=nullptr;inorder(root);if(first!=nullptr&&second!=nullptr){inttmp=first->val;first->val=second->val;second->val=tmp;}}private:TreeNode*first;TreeNode*second;TreeNode*prev;voidinorder(TreeNode*node){if(node==nullptr)return;inorder(node->left);if(prev!=nullptr&&prev->val>node->val){if(first==nullptr)first=prev;second=node;}prev=node;inorder(node->right);}};