力扣每日一题99:恢复二叉搜索树
2023-12-31 13:35:03
题目
给你二叉搜索树的根节点?root
?,该树中的?恰好?两个节点的值被错误地交换。请在不改变其结构的情况下,恢复这棵树?。
示例 1:
输入:root = [1,3,null,null,2] 输出:[3,1,null,null,2] 解释:3 不能是 1 的左孩子,因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2:
输入:root = [3,1,4,null,null,2] 输出:[2,1,4,null,null,3] 解释:2 不能在 3 的右子树中,因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
提示:
- 树上节点的数目在范围?
[2, 1000]
?内 -231 <= Node.val <= 231 - 1
进阶:使用?O(n)
?空间复杂度的解法很容易实现。你能想出一个只使用?O(1)
?空间的解决方案吗?
通过次数
146.4K
提交次数
242.3K
通过率
60.5%
分析
二叉搜索树中序遍历是有序的(a[i]<a[i+1]),错误交换两个节点后,存在两个地方(a[i]>a[i+1]),如果两个地方重复了,那就是一个地方。
所以我们只要根据a[i]>a[i+1]这一特性找的错误交换的两个点换回来就行了。
普通方法:设置数组存放数据。时间O(N),空间O(N)
中序遍历依次二叉树,同时将每个节点的地址和值分别放在一个数组里。然后再遍历记录数值的数组,找到要交换的两个位置。
class Solution {
public:
void dfs(int arr[],TreeNode* adress[],int &pos,TreeNode* root)
{
if(!root) return;
dfs(arr,adress,pos,root->left);
arr[pos]=root->val;
adress[pos]=root;
pos++;
dfs(arr,adress,pos,root->right);
}
void recoverTree(TreeNode* root) {
TreeNode *adress[1000];
int arr[1000];
int pos=0;
dfs(arr,adress,pos,root);
int t1=-1,t2=0;
for(int i=0;i<pos-1;i++)
{
//cout<<arr[i]<<",";
if(arr[i]>arr[i+1])
{
if(t1==-1)
{t1=i;t2=i+1;}
else t2=i+1;
}
}
//cout<<arr[pos-1];
//cout<<"\nt1="<<t1<<" t2="<<t2;
int t=adress[t1]->val;
adress[t1]->val=adress[t2]->val;
adress[t2]->val=t;
}
};
进阶:中序遍历,栈记录前驱。时间O(N),空间(H),H为树的高度。
前面的方法是找到要交换连个节点的地址,然后交换值。我们用了一个数组记录所有节点的地址。其实我们就交换两个数,记录两个地址就行了。用二叉树的迭代法遍历可以用栈存放遍历的前驱,刚好符合了i和i+1的关系。下面是官方题解。
class Solution {
public:
void recoverTree(TreeNode* root) {
stack<TreeNode*> stk;
TreeNode* x = nullptr;
TreeNode* y = nullptr;
TreeNode* pred = nullptr;
while (!stk.empty() || root != nullptr) {
while (root != nullptr) {
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
if (pred != nullptr && root->val < pred->val) {
y = root;
if (x == nullptr) {
x = pred;
}
else break;
}
pred = root;
root = root->right;
}
swap(x->val, y->val);
}
};
高阶:Morris遍历,时间O(N),空间O(1)
废话不多说,看官方题解的代码。
class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode *x = nullptr, *y = nullptr, *pred = nullptr, *predecessor = nullptr;
while (root != nullptr) {
if (root->left != nullptr) {
// predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
predecessor = root->left;
while (predecessor->right != nullptr && predecessor->right != root) {
predecessor = predecessor->right;
}
// 让 predecessor 的右指针指向 root,继续遍历左子树
if (predecessor->right == nullptr) {
predecessor->right = root;
root = root->left;
}
// 说明左子树已经访问完了,我们需要断开链接
else {
if (pred != nullptr && root->val < pred->val) {
y = root;
if (x == nullptr) {
x = pred;
}
}
pred = root;
predecessor->right = nullptr;
root = root->right;
}
}
// 如果没有左孩子,则直接访问右孩子
else {
if (pred != nullptr && root->val < pred->val) {
y = root;
if (x == nullptr) {
x = pred;
}
}
pred = root;
root = root->right;
}
}
swap(x->val, y->val);
}
};
文章来源:https://blog.csdn.net/m0_73441691/article/details/135314667
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!