（难度Hard） Problem 99. Recover Binary Search Tree（恢复BST）

Recover Binary Search Tree

Hard

## Description

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]

1
/
3
\
2

Output: [3,1,null,null,2]

3
/
1
\
2

Example 2:

Input: [3,1,4,null,null,2]

3
/ \
1   4
/
2

Output: [2,1,4,null,null,3]

2
/ \
1   4
/
3

• A solution using O( _n_ ) space is pretty straight forward.
• Could you devise a constant space solution?

## 题解

c++
class Solution {
public:
// 中序遍历
void inorder(vector& vt, TreeNode* node) {
if (node == nullptr) return ;
if (node->left != nullptr) {
inorder(vt, node->left);
}
vt.push_back(node->val);
if (node->right != nullptr) {
inorder(vt, node->right);
}
}

// 还原二叉搜索树，其实原理很简单，就是遍历树，找到等于x的位置赋值成y，找到等于y的位置赋值成x
// 因为二叉搜索树当中不会有重复的元素，所以修复完成之后就可以return了
void recover(TreeNode* node, int num, int x, int y) {
if (num == 0 || node == nullptr) return ;
if (node->val == x || node->val == y) {
node->val = node->val == x ? y : x;
num--;
}`