原题
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
Follow up:
- A solution using O(n) space is pretty straight forward.
- Could you devise a constant space solution?
Accepted
视频讲解
B站视频源
YouTube视频源
如果大家有兴趣一起侃侃数据结构与算法，那么可以通过下面的微信号或者微信公众号给我留言（要带上自己的微信ID哦）：
微信公众号（推荐）：ihuxublog（胡小旭博客）
微信：genialx
如果你喜欢我的视频，可以到B站或者Youtube关注我~
分析题目
解法一 排序
考虑将错误的二叉树进行一次中序遍历，并将遍历的结果保留到数组中。然后将问题转换成在一个线性数组中查找错误的两个元素的值。最后，再遍历一次二叉搜索树进行恢复即可。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
int x = -1, y = -1;
void inorder(TreeNode* node, vector<int>& nums) {
if (node == nullptr) return;
inorder(node->left, nums);
nums.push_back(node->val);
inorder(node->right, nums);
}
// 1 2 3 4 5
// 1 3 2 4 5
// 1 4 3 2 5
void findTwoSwappedNums(vector<int>& nums) {
for (int i = 0; i < nums.size() - 1; ++i) {
if (nums[i] > nums[i + 1]) {
y = nums[i + 1];
if (x == -1) x = nums[i];
else break;
}
}
}
void recover(TreeNode* node) {
if (node == nullptr) return;
if (node->val == x) {
node->val = y;
} else if (node->val == y) {
node->val = x;
}
recover(node->left);
recover(node->right);
}
public:
void recoverTree(TreeNode* root) {
vector<int> nums{};
inorder(root, nums);
findTwoSwappedNums(nums);
recover(root);
}
};复杂度分析
时间复杂度：O(n)
空间复杂度：O(n)
解法二
即在递归中序遍历二叉搜索树时，利用前驱节点，及时的判断当前节点与前驱节点相对关系的合法性，并将错误的节点保留下来。最后，交换两个错误的节点中的值。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
TreeNode *x = nullptr, *y = nullptr, *pred = nullptr;
void inorder(TreeNode* node) {
if (node == nullptr) return;
inorder(node->left);
if (pred != nullptr && node->val < pred->val) {
y = node;
if (x == nullptr) x = pred;
else return;
}
pred = node;
inorder(node->right);
}
public:
void recoverTree(TreeNode* root) {
inorder(root);
int tmp = x->val;
x->val = y->val;
y->val = tmp;
}
};复杂度分析
时间复杂度：O(n)
空间复杂度：O(\log n)
欢迎分享，引用。若转载，请联系我，谢谢配合。 本文地址：https://qoogle.top/xiaoxu-explain-leetcode-99-recover-binary-search-tree/