代码编织梦想

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档


前言

最近跟二叉搜索树杠上了、、

一、题目

恢复二叉搜索树

给你二叉搜索树的根节点 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) 空间的解决方案吗?

二、思路

首先,解题的关键在于二叉搜索树的性质:对二叉搜索树进行中序遍历,得到的值序列是递增有序的。
如果错误地交换了两个节点,等价于在这个值序列中交换了两个值,破坏了值序列的递增性。
因此,只需要在对二叉树进行遍历的时候,找到所有非递增的“问题结点”即可(即某结点的值小于其前结点,root.val<root.left)
如果只能找到一个问题结点,就把此结点与其前结点的值交换;如果找到两个问题结点,就把第一个问题结点前的值第二个问题结点互换即可
时间复杂度:O(N),其中 N 为二叉搜索树的高度。Morris 遍历中每个节点会被访问两次,因此总时间复杂度为 O(2N)=O(N)O(2N)=O(N)。
空间复杂度:O(1)。
注意,遍历时,为了在递归中保留上一个结点的指针,指针必须设置为全局变量(或引用类型),否则无法保存,会造成回溯

三、代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        question_node=[] #问题结点列表
        q1=[None] #保证全局可用,因为递归同步不了变量
        #递归实现遍历
        def traverse(root):#遍历中指向上一个节点的指针  
            if(root == None):
                return
            traverse(root.left) #遍历
            if(q1[0] and q1[0].val > root.val):
                question_node.append([q1[0],root])#有问题的前一个结点和有问题的结点
            q1[0]=root #指针向后移动
            traverse(root.right) #遍历
        #遍历
        traverse(root) 
        #交换问题结点的值
        if(len(question_node) == 1):
            question_node[0][0].val,question_node[0][1].val=question_node[0][1].val,question_node[0][0].val
        else:
            question_node[0][0].val,question_node[1][1].val=question_node[1][1].val,question_node[0][0].val


在这里插入图片描述

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_46447549/article/details/127144666

leetcode450——删除二叉搜索树中的节点_清風逐尘乀的博客-爱代码爱编程

我的LeetCode代码仓:https://github.com/617076674/LeetCode 原题链接:https://leetcode-cn.com/problems/delete-node-in-a-bst/description/ 题目描述: 知识点:二分搜索树 思路:二分搜索树删除节点的经典操作 本题考查的完全是数据结构的知

Java实现 LeetCode 99 恢复二叉搜索树-爱代码爱编程

99. 恢复二叉搜索树 二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下,恢复这棵树。 示例 1: 输入: [1,3,null,null,2] 1 / 3 \ 2 输出: [3,1,null,null,2] 3 / 1 \ 2 示例 2: 输入: [3,1,4,null,nul

LeetCode——验证二叉搜索树-爱代码爱编程

题目: 给定一个二叉树,判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征: 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1: 输入:      2     / \   1   3 输出: true 示例 2: 输入:      5

Leetcode 96. 不同的二叉搜索树-爱代码爱编程

Leetcode 96. 不同的二叉搜索树 1、问题分析2、问题解决3、总结 1、问题分析 题目链接:https://leetcode-cn.com/problems/unique-binary-search-trees/   可以使用动态规划求解,总体思路就是固定根节点,然后求左右子节点各有多少种情况,将结果相乘,这里注意单位个数为 1。代

⭐算法入门⭐《二叉树 - 二叉搜索树》中等07 —— LeetCode 501. 二叉搜索树中的众数-爱代码爱编程

文章目录 一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知 一、题目 1、题目描述   给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。  样例输入: [1,null,2,2]  样例输出: 2 2、基础框架

⭐算法入门⭐《二叉树 - 二叉搜索树》中等08 —— LeetCode 669. 修剪二叉搜索树-爱代码爱编程

文章目录 一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知 一、题目 1、题目描述   给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中

Leetcode打卡——二叉搜索树(共8题)-爱代码爱编程

二叉搜索树(BST)是二叉树的一种特殊表示形式,它满足如下特性: 每个节点中的值必须大于(或等于)存储在其左侧子树中的任何值。 每个节点中的值必须小于(或等于)存储在其右子树中的任何值。 1.Leetcode98. 验证二叉搜索树 法一:利用二叉树的性质,根结点的值大于左子树上的点,小于右子树上的点 const long long MAX=2e3

Leetcode刷题笔记——剑指 Offer 33. 二叉搜索树的后序遍历序列(中等)-爱代码爱编程

文章目录 题目描述方法一:递归分治复杂度分析C++代码实现方法二:辅助单调栈复杂度分析C++代码实现 题目描述 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。 注:1.后序遍历定义: [ 左子树 | 右子树 | 根节点 ] ,即遍历顺序为

【LeetCode】恢复二叉搜索树-爱代码爱编程

#LeetCode每日一题【二叉树专题】 恢复二叉搜索树 https://leetcode-cn.com/problems/recover-binary-search-tree/分析 二叉搜索树一个重要的特性就是其中序遍历的结果是升序的,二叉搜索树被交换了两个节点,也就等同于升序数组中被交换了两个数。如何找到升序数组中被交换的两个数? 假设一个数组 [1

LeetCode--二叉搜索树-爱代码爱编程

LeetCode98. Validate Binary Search Tree验证二叉搜索树 一、题目 给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下: 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1:

⭐算法入门⭐《二叉树 -爱代码爱编程

文章目录 一、题目1、题目描述2、基础框架3、原题链接 二、解题报告1、思路分析2、时间复杂度3、代码详解 三、本题小知识四、加群须知 一、题目 1、题目描述   给定二叉搜

⭐算法入门⭐《二叉树 -爱代码爱编程

文章目录 一、题目1、题目描述2、基础框架3、原题链接 二、解题报告1、思路分析2、时间复杂度3、代码详解 三、本题小知识四、加群须知 一、题目 1、题目描述   返回与给定

⭐算法入门⭐《二叉树 -爱代码爱编程

文章目录 一、题目1、题目描述2、基础框架3、原题链接 二、解题报告1、思路分析2、时间复杂度3、代码详解 三、本题小知识四、加群须知 一、题目 1、题目描述   给你一棵二

⭐算法入门⭐《二叉树 -爱代码爱编程

文章目录 一、题目1、题目描述2、基础框架3、原题链接 二、解题报告1、思路分析2、时间复杂度3、代码详解 三、本题小知识四、加群须知 一、题目 1、题目描述   实现一个函