商洛市网站建设_网站建设公司_UX设计_seo优化

输入：二叉搜索树根节点root，其中恰好有两个节点的值被错误交换。

要求：在不改变树结构的情况下恢复 BST（只允许改节点值）。

输出：无（原地修改root）。

思路：

BST 的中序遍历应该是严格递增序列。
一旦有两个节点值被交换，中序序列里就会出现“乱序”，表现为逆序对：

• 正常：... a < b < c < d ...
• 交换后可能出现：
  • 相邻交换：只出现1 次逆序（例如... a < c < b < d ...，在c > b处逆序）
  • 不相邻交换：出现2 次逆序（例如... a < d < c < b ...，会在d > c、c > b两处逆序）

所以我们中序遍历时维护prev（上一个访问的节点）：

1. 若发现prev->val > node->val，说明出现逆序。
2. 第一次逆序：first = prev（大的那个）
3. 每次逆序都更新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);}};