刷题笔记

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

一、题目描述:

给你二叉搜索树的根节点 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;
    }

}

四、总结:

image.png

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

希望对你有帮助

期待下次再见~

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

相关文章
|
存储
LeetCode刷题笔记
LeetCode刷题笔记
153 2
|
存储 算法 C语言
日常刷题篇(入门)
我从简单到难,一起走上漫漫刷题路! 我会持续在我的博客中更新我每天刷题的内容! 相互交流!
日常刷题篇(入门)
我从简单到难,一起走上漫漫刷题路! 我会持续在我的博客中更新我每天刷题的内容! 相互交流!
|
前端开发
牛客前端宝典——刷题 ##Day6
🏆编程就像我们平常做题一样,如果只是一味的学习不去做题的话所得到的效果微乎其微。
100 0
牛客前端宝典——刷题 ##Day6
|
前端开发 JavaScript
牛客前端宝典——刷题 ##Day9
🏆编程就像我们平常做题一样,如果只是一味的学习不去做题的话所得到的效果微乎其微。
134 0
牛客前端宝典——刷题 ##Day9
|
文字识别 前端开发 开发者
牛客前端宝典——刷题 ##Day5
🏆编程就像我们平常做题一样,如果只是一味的学习不去做题的话所得到的效果微乎其微。
125 0
牛客前端宝典——刷题 ##Day5