leetcode 99. 恢复二叉搜索树

港控/mmm° 2023-06-08 03:19 94阅读 0赞

**中序遍历，弄在数组里面，再弄个数组复制一份排好序**  
**比较哪里错了，换回来**  
**中序遍历的时候用map存一下数字的地址（默认没有重复元素）**

class Solution { 
    public:
        vector<int> zhong;
        map<int,TreeNode*> dizhi;
        void recoverTree(TreeNode* root) { 
            if( root == nullptr ){ 
                return;
            }
            zhongxu(root);
            vector<int>paizhong(zhong);
            sort(paizhong.begin(),paizhong.end());
            //debug( zhong.size() )
            for(int i=0;i<zhong.size();i++){ 
                if(zhong[i] != paizhong[i]){ 
                    swap( dizhi[ zhong[i] ]->val,dizhi[ paizhong[i] ]->val);
                    //cout<<"1"<<endl;
                    break;
                }
    
            }
        }
        void zhongxu( TreeNode * rt ){ 
            if( rt!= nullptr ){ 
                zhongxu( rt->left );
                zhong.push_back(rt->val);
                dizhi[rt->val] = rt;
                zhongxu( rt->right );
            }
        }
    };

![在这里插入图片描述][20191015231038836.png]

[20191015231038836.png]: /images/20230531/f3e87a029f3d479793fddf619c032d4b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，94人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 99. 恢复二叉搜索树

中序遍历，弄在数组里面，再弄个数组复制一份排好序比较哪里错了，换回来中序遍历的时候用map存一下数字的地址（默认没有重复元素） class Solutio

港控/mmm°/ 2023年06月08日 03:19/ 0 赞/ 95 阅读

相关恢复二叉搜索树

恢复二叉搜索树 ![format_png][] ![format_png 1][] -------------------- / 二叉树类定义 /

迈不过友情╰/ 2023年02月23日 07:51/ 0 赞/ 66 阅读

相关 LeetCode 98验证二叉搜素树(中序遍历)&99恢复二叉搜索树

> 微信搜一搜：`bigsai` > [大家都在关注的刷题、学习数据结构和算法宝藏项目][Link 1] > 关注回复进群即可加入力扣打卡群，欢迎划水。近期打卡：

柔情只为你懂/ 2023年01月01日 14:49/ 0 赞/ 130 阅读

相关 [Leetcode][第99题][JAVA][恢复二叉搜索树][中序遍历]

【问题描述】\[困难\] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6L

亦凉/ 2022年11月25日 10:27/ 0 赞/ 106 阅读

相关【LeetCode】二叉树问题：二分搜索树

二分搜索树 [235. 二叉搜索树的最近公共祖先][235.] 难度简单532收藏分享切换为英文接收动态反馈给定一个二叉搜索树, 找到该树中两个指定节点的最近公

快来打我*/ 2022年10月29日 09:12/ 0 赞/ 191 阅读

相关 99. 恢复二叉搜索树

> 给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。 > > ![watermark_type_ZmFuZ3poZW5

女爷i/ 2022年10月08日 02:28/ 0 赞/ 97 阅读

相关 leetcode 669 修剪二叉搜索树

前言题目：[669. 修剪二叉搜索树][669.] 参考题解：[修剪二叉搜索树-力扣官方题解][-] -------------------- 提交代码看

╰+攻爆jí腚メ/ 2022年09月12日 08:49/ 0 赞/ 149 阅读

相关 [Leetcode][python]Recover Binary Search Tree/恢复二叉搜索树

题目大意一颗二叉查找树中的某两个节点被错误的交换了，需要恢复成原来的正确的二叉查找树。挑战：是要求空间复杂度为常数空间。空间复杂度为O(N)是常规解法。解题思

本是古典何须时尚/ 2022年06月11日 07:10/ 0 赞/ 154 阅读

相关 [LeetCode] 二叉搜索树判定

出处 > [验证二叉搜索树][Link 1] 分析 > 给定一个二叉树，判断其是否是一个有效的二叉搜索树。 > 假设一个二叉搜索树具有如下特征： > \-

妖狐艹你老母/ 2022年05月18日 10:11/ 0 赞/ 193 阅读

相关 leetcode【98】验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所

太过爱你忘了你带给我的痛/ 2021年10月03日 01:36/ 0 赞/ 267 阅读