LeetCode 0099 - Recover Binary Search Tree
# Hints
DFS
中序遍历
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard | or |
You are given the root
of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
Follow up: A solution using O(n)
space is pretty straight forward. Could you devise a constant space solution?
Example 1:
Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.
Example 2:
Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.
Constraints:
The number of nodes in the tree is in the range .
# 题意
给定一棵二叉查找树,树上有两个节点的值被交换了,要求找到这两个节点并恢复未交换时的树。不允许改变原先的树结构。
# 题解
本题的解决思路和 LeetCode 0098 类似。二叉查找树的中序遍历序列是一个严格递增序列,交换两个节点的值等价于交换此序列中的两个元素。
不难发现,一次交换最多产生两组相邻逆序对。不妨设序列下标从 到 ,则最多存在两个不同的下标 满足 。不妨设两个下标为 ,以 [1 2 3 4 5]
为例:
swap before after i j
2, 5 [1 2 3 4 5] [1 5 3 4 2] 3 5
2, 4 [1 2 3 4 5] [1 4 3 2 5] 3 4
2, 3 [1 2 3 4 5] [1 3 2 4 5] 3 -
显然对于下标 ,元素 和 即为被交换的节点值。
因此我们只需进行中序遍历即可。下面的 AC 代码 1 显式地求出遍历序列后进行恢复,而 AC 代码 2 则在 DFS 的同时就完成了恢复,前者时间更优(递归函数调用传参更少)且更直观,后者节约了大小为 的额外空间。
但是上述实现都不能满足 额外空间的要求,因为递归调用栈也是 的,这也是此题设为 Hard 的理由,否则只能是个 Medium 。使用 Morris 遍历算法实现中序遍历即可满足要求。
# AC代码(1)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode * left;
* TreeNode * right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode * left, TreeNode * right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void recoverTree(TreeNode * root) {
// DFS
TreeNode * prv = nullptr;
vector<TreeNode *> vec;
dfs(root, vec);
// 恢复
TreeNode * err1 = nullptr;
TreeNode * err2 = nullptr;
for (int i = 1; i < vec.size(); i ++) {
if (vec[i]->val <= vec[i - 1]->val) {
if (err1 == nullptr) {
err1 = vec[i - 1];
}
err2 = vec[i];
}
}
swap(err1->val, err2->val);
}
// 深度优先搜索:中序遍历
void dfs(TreeNode * p, vector<TreeNode *> & vec) {
if (p->left != nullptr) dfs(p->left, vec);
vec.push_back(p);
if (p->right != nullptr) dfs(p->right, vec);
}
};
# AC代码(2)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode * left;
* TreeNode * right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode * left, TreeNode * right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void recoverTree(TreeNode * root) {
// DFS
TreeNode * prv = nullptr;
TreeNode * err1 = nullptr;
TreeNode * err2 = nullptr;
dfs(root, prv, err1, err2);
// 恢复
swap(err1->val, err2->val);
}
// 深度优先搜索:中序遍历
void dfs(TreeNode * p, TreeNode * & prv, TreeNode * & err1, TreeNode * & err2) {
// 递归左子树
if (p->left != nullptr) dfs(p->left, prv, err1, err2);
// 更新答案
if (prv != nullptr && p->val <= prv->val) {
if (err1 == nullptr) {
err1 = prv;
}
err2 = p;
}
prv = p;
// 递归右子树
if (p->right != nullptr) dfs(p->right, prv, err1, err2);
}
};
# AC代码(Morris 遍历)(待补)
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01