力扣每日一题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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。