更文

简介: 更文

一、题目描述:

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

示例 1:

img

输入:root = [1,3,null,null,2]
输出:[3,1,null,null,2]
解释:3 不能是 1 的左孩子,因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2:

img

输入: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) 空间的解决方案吗?

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/recover-binary-search-tree

二、思路分析:

一个合格的二叉搜索树的中序遍历一定是个严格递增的序列,如果发生了交换,可能会有两种情况:

交换的是相邻的节点,即发现一个节点值小于其前一个节点值时,这两个节点就刚好是被交换的。
交换的是不相邻的节点,即发现了两次异常,第一次是:A节点值大于其后一个节点值,第二次是:B节点值小于其前一个节点值。A和B就是被交换的两个节点。

首先,二叉搜索树的中序遍历出的节点是有序的
其次,并没有说交换的节点是相邻的,所以不能直接交换 pre->val 与 root->val
所以我们要找到两个不符合前一个节点值小于后一个节点值的点。
最后,将两节点交换。
过程:第一次找到(前大后小),由于x == nullptr,所以x = pre,之后的遍历都不会再对x产生影响,
只会改变y的值。

三、AC 代码:

class Solution {
    public void recoverTree(TreeNode root) {
        Deque<TreeNode> stk = new ArrayDeque<>();
        TreeNode x = null, y = null, pre = null;
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.offer(root);
                root = root.left;
            }
            root = stk.pollLast();
            if (pre != null && pre.val > root.val) {
                y = root;
                if (x == null) {
                    x = pre;
                } else {
                    break;
                }
            }
            pre = root;
            root = root.right;
        }
        // 交换节点
        int tmp = x.val;
        x.val = y.val;
        y.val = tmp;
    }

}
AI 代码解读

四、总结:

image.png

掘友们,解题不易,留下个赞或评论再走吧!谢啦~ 💐

希望对你有帮助

期待下次再见~

🌇 点赞 👍 收藏 ⭐留言 📝 一键三连 ~关注Jam,从你我做起!

目录
打赏
0
0
0
0
4
分享
相关文章
高校学生参加飞天加速计划
linux与服阿里云服务器ECS, 阿里云服务器为提供了强大云计算能力。并且平台有很多开发者的使用教程,让我们新手也能很快上手去开发一些网站,希望更多的学生能够加入到阿里云,学习+实战让自己变得更强。
【Python】已解决:ModuleNotFoundError: No module named ‘nltk’
【Python】已解决:ModuleNotFoundError: No module named ‘nltk’
233 0
【Python】已解决:ModuleNotFoundError: No module named ‘nltk’
《PolarDB for PostgreSQL源码与应用实战》——PolarDB-PostgreSQL开源核心Feature介绍(1)
《PolarDB for PostgreSQL源码与应用实战》——PolarDB-PostgreSQL开源核心Feature介绍(1)
404 0
PolarDB MySQL企业版与标准版功能对比:如何选择适合您的版本?
随着数字化时代的到来,企业对于数据处理的需求越来越高,而数据库作为数据处理的核心,其性能和成本成为了企业关注的焦点。阿里云全新推出的PolarDB MySQL企业版和标准版,以全新的架构和优化,为企业提供了高性能、低成本的数据库解决方案。但在功能上,这两个版本有很多差异,我们该如何选择呢?
189 2
|
4月前
|
深入解析:JS与Vue中事件委托(事件代理)的高效实现方法
深入解析:JS与Vue中事件委托(事件代理)的高效实现方法
95 0
【Java】智慧工地管理系统源代码,支持二次开发,SaaS模式
智慧工地系统围绕工程现场人、机、料、法、环及施工过程中质量、安全、进度、成本等各项数据满足工地多角色、多视角的有效监管,实现工程建设管理的降本增效。
114 1
|
9月前
[Qt5] 鼠标中心为基准缩放图像(halcon实现)
[Qt5] 鼠标中心为基准缩放图像(halcon实现)
286 0
[Unity3D]Unity+Android交互教程——让手机"动"起来
想要用Unity实现一个二维码扫描的功能,然后网上找插件,找到一个貌似叫EasyCodeScanner,但下载下来用用,真不好使,一导入运行就报错,调好错了再运行发现点按钮没反应,反复试了几遍发现还是没反应,没办法看源码,结果发现只实现了IOS部分,没有Android部分,我屮艸芔茻.
1667 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等