当前位置： 面试刷题>> 恢复二叉搜索树 (经典算法题500道)
### 题目描述
**恢复二叉搜索树**
给定一个二叉搜索树（BST）的两个节点的值，这两个节点分别被错误地交换了位置，导致BST不再保持二叉搜索树的性质。请编写一个算法来恢复这个BST，要求只能使用恒定的额外空间（即 O(1) 额外空间）。
**注意**：
1. 树中的节点数量在范围 `[2, 1000]` 内。
2. 每个节点的值都是唯一的，且在范围 `[1, 10^4]` 内。
### 示例
假设给定的BST如下（用中序遍历表示，以便更容易看出问题）：
```
3
\
1
/
2
```
显然，1 和 2 被错误地交换了位置。恢复后的BST应为：
```
2
\
1
/
3
```
### 解题思路
为了找到被错误交换的节点并恢复BST，我们可以使用中序遍历（左-根-右）。在BST的中序遍历中，节点应该按照升序排列。因此，错误交换的两个节点将会是中序遍历中相邻但顺序相反的两个节点。
我们可以使用两个指针（prev 和 first）来跟踪中序遍历中的前一个节点和第一个顺序错误的节点。当遇到第一个顺序错误的节点时，我们还需要找到第二个顺序错误的节点（即 prev 在下一次迭代时的值）。然后，我们交换这两个节点的值。
### 示例代码
#### PHP
```php
class TreeNode {
public $val;
public $left;
public $right;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
function recoverTree($root) {
$prev = null;
$first = null;
$second = null;
inorder($root, $prev, $first, $second);
// 交换两个节点的值
$temp = $first->val;
$first->val = $second->val;
$second->val = $temp;
}
function inorder($node, &$prev, &$first, &$second) {
if ($node === null) return;
inorder($node->left, $prev, $first, $second);
if ($prev !== null && $prev->val > $node->val) {
if ($first === null) {
$first = $prev;
}
$second = $node;
}
$prev = $node;
inorder($node->right, $prev, $first, $second);
}
```
#### Python
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def recoverTree(root):
prev, first, second = None, None, None
def inorder(node):
nonlocal prev, first, second
if not node:
return
inorder(node.left)
if prev and prev.val > node.val:
if not first:
first = prev
second = node
prev = node
inorder(node.right)
inorder(root)
first.val, second.val = second.val, first.val
```
#### JavaScript
```javascript
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
function recoverTree(root) {
let prev = null, first = null, second = null;
function inorder(node) {
if (!node) return;
inorder(node.left);
if (prev && prev.val > node.val) {
if (!first) {
first = prev;
}
second = node;
}
prev = node;
inorder(node.right);
}
inorder(root);
[first.val, second.val] = [second.val, first.val];
}
```
**码小课网站中有更多相关内容分享给大家学习**，包括数据结构与算法的各种知识，以及实战应用等。