算法题:99.恢复二叉搜索树

这篇具有很好参考价值的文章主要介绍了算法题:99.恢复二叉搜索树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

(为不影响大家的观感,完整题目附在了最后)

算法题:99.恢复二叉搜索树,数据结构与算法,leetcode&牛客,Python精修,算法,二叉树,python,数据结构,搜索二叉树,恢复搜索二叉树

二叉搜索树的定义

二叉搜索树(BST,Binary Search Tree),也称二叉排序树或二叉查找树。
二叉搜索树:一棵二叉树,可以为空;如果不为空,满足以下性质:

  1. 非空左子树的所有键值小于其根结点的键值。
  2. 非空右子树的所有键值大于其根结点的键值。
  3. 左、右子树都是二叉搜索树。

恢复二叉搜索树的解法分析

由二叉搜索树的定义可推知:二叉搜索树的中序遍历结果一定是严格由小到大排序的。由于“恢复二叉搜索树”的题目中指出“恰好两个节点的值被错误地交换”,那么我们只要找出破坏了这个顺序的两个节点,交换其节点值就可以了。

阅读本篇内容时,可结合本人在另一个博客中详细分析的 Morris 中序遍历方法:

算法:实现中序遍历(3种方法:递归、迭代、Morris)-CSDN博客

本题最优解法是采用 Morris 中序遍历方法,也就是题目进阶要求里的使用 O(1) 空间的解决方案,本人之前掌握的 Morris 中序遍历方法,在遍历的过程中是会改变树的结构的,会影响到层序遍历的结果,而本题要求的输出是层序遍历的,因此改变树的结构不可行。为此,我又学习了另一种最终不会改变树的结构的 Morris 中序遍历方法,我在这里重新贴一下代码,具体的原理分析还请看我上面分享的博文,那里面写的很详细,步骤都有画出来。

class Solution(object):
    def inorderTraversal(self, root):
        res = []
        while root:
            if root.left:
                temp = root.left
                while temp.right and temp.right != root:
                    temp = temp.right
                if not temp.right:
                    temp.right = root
                    root = root.left
                else:  # temp.right == root 的情况
                    res.append(root.val)
                    temp.right = None
                    root = root.right
            else:
                res.append(root.val)
                root = root.right
        return res

恢复二叉搜索树的完整代码

接下来,只要在其中加一些判断语句,找出中序遍历后不服从由小到大顺序的两个结点进行值的交换即可,完整测试代码如下:(提交时只需要提交recoverTree()函数代码,层序遍历的输出是力扣自动帮忙完成的)

# 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):
        x, y = None, None  # 设置两个变量,代表被错误交换的两个节点
        pre = None
        while root:
            if root.left:
                tmp = root.left
                while tmp.right and tmp.right != root:
                    tmp = tmp.right
                if tmp.right is None:
                    tmp.right = root
                    root = root.left
                else:  # temp.right == root 的情况
                    if pre and pre.val > root.val:  # 新加入的判断语句
                        # 假设最先遇到的两个不符合顺序的结点就是最终要找的两个节点
                        if not x:  
                            x = pre
                            y = root
                        else:  # 如果后面又遇到了不符合顺序的结点,则 y 需要变
                            y = root
                    pre = root
                    tmp.right = None
                    root = root.right
            else:
                if pre and pre.val > root.val:  # 新加入的判断语句
                    if not x:
                        x = pre
                        y = root
                    else:
                        y = root
                pre = root
                root = root.right

        if x and y:
            x.val = x.val ^ y.val
            y.val = x.val ^ y.val
            x.val = x.val ^ y.val

    def levelOrder(self, root):  # 层序排列
        if not root:
            return []
        res = []
        queue = [root]
        while len(queue) > 0:
            size = len(queue)
            temp = []
            for i in range(size):  # 确保了每层的结点值在同一个数组内
                # 通过append、pop(0)的方法用数组构造了一个先进先出的列表
                node = queue.pop(0)
                temp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(temp)

        return res


if __name__ == '__main__':
    # 创建一个二叉树
    tree = TreeNode(3)
    tree.left = TreeNode(1)
    tree.right = TreeNode(4)
    tree.right.left = TreeNode(2)

    # 执行中序遍历
    sol = Solution()
    sol.recoverTree(tree)
    print(sol.levelOrder(tree))  # [[2], [1, 4], [3]]

 如果对这里的层序遍历的代码感兴趣,可以看我的这篇博文:

算法题:二叉树的层序遍历-CSDN博客

恢复二叉搜索树的完整题目

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

示例 1:

算法题:99.恢复二叉搜索树,数据结构与算法,leetcode&牛客,Python精修,算法,二叉树,python,数据结构,搜索二叉树,恢复搜索二叉树

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

示例 2:

算法题:99.恢复二叉搜索树,数据结构与算法,leetcode&牛客,Python精修,算法,二叉树,python,数据结构,搜索二叉树,恢复搜索二叉树

输入:root = [3,1,4,null,null,2]
输出:[2,1,4,null,null,3]
解释:2 不能在 3 的右子树中,因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示:

  • 树上节点的数目在范围 [2, 1000] 内
  • -2^31 <= Node.val <= 2^31 - 1

进阶:使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗?文章来源地址https://www.toymoban.com/news/detail-739685.html

到了这里,关于算法题:99.恢复二叉搜索树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法与数据结构--二叉搜索树与自平衡二叉搜索树

    注:字典的 \\\"member运算\\\" 指的是检查字典中是否存在某个特定的键的操作,即查询操作。 如果我们使用数组来实现字典/map,虽然使用二分法查询也可以达到logn,但是的话插入和删除太慢了。使用链表实现的话虽然插入和删除是O(1),但是查询的话达到了O(n),也不可取。 因此人

    2024年02月04日
    浏览(37)
  • Java数据结构与算法:二叉搜索树

    Java数据结构与算法:二叉搜索树 大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! 在计算机科学中,二叉搜索树(Binary Search Tree,简称BST)是一种常见的树形数据结构,它具有良好的查找和插入性能。每

    2024年01月24日
    浏览(44)
  • 数据结构与算法-基础(十)平衡二叉搜索树

    摘要 二叉搜索树的特性-节点的左侧部分比它小,右侧部分比它大,使得二叉搜索树在查找节点有 二分法 的效果,也提高了它的添加和删除处理,毕竟添加和删除也是先查找位置,然后再处理。 平衡二叉搜索树 就是持续保证这样的高效性,进入正题: 二叉搜索树 在添加或

    2024年02月08日
    浏览(46)
  • 【算法与数据结构】226、LeetCode翻转二叉树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :这道题的思路很简单,本质上就是遍历每一个节点,然后交换左右节点。我们可以用前中后遍历或者是层次遍历法来做,参考这两篇文章,【算法与数据结构】144、94、145LeetCode二

    2024年02月16日
    浏览(40)
  • 【算法与数据结构】654、LeetCode最大二叉树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树这两道题有些类似,相关代码可以互相参考,本题明示了要用递归来做,那么递归三要素不可缺少: 输入参数和返

    2024年02月09日
    浏览(44)
  • 【算法与数据结构】236、LeetCode二叉树的最近公共祖先

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 : 根据定义,最近祖先节点需要遍历节点的左右子树,然后才能知道是否为最近祖先节点。 那么这种需求是先遍历左右节点,然后遍历中间节点,属于左右中的后序遍历模式 。因此

    2024年02月09日
    浏览(37)
  • 数据结构与算法(三):树论(树形结构、二叉树、二叉搜索树、红黑树、Btree&B+Tree、赫夫曼树、堆树)

    树论(树形结构、二叉树、二叉搜索树、红黑树、Btree、B+Tree、赫夫曼树、堆树) 在树形结构里面重要的术语: 结点:树里面的元素。 父子关系:结点之间相连的边 子树:当结点大于1时,其余的结点分为的互不相交的集合称为子树 度:一个结点拥有的子树数量称为结点的

    2024年02月01日
    浏览(93)
  • 【算法与数据结构】222、LeetCode完全二叉树的节点个数

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :利用层序遍历,然后用num++记录节点数量。其他的例如递归法和迭代法也是如此。    层序遍历程序如下 : 复杂度分析: 时间复杂度: O ( n ) O(n) O ( n ) 。 空间复杂度: O ( n )

    2024年02月15日
    浏览(47)
  • 数据结构与算法之二叉树: Leetcode 111. 二叉树的最小深度 (Typescript版)

    二叉树的最小深度 https://leetcode.cn/problems/minimum-depth-of-binary-tree/ 描述 就 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。 示例 1 示例 2 提示 树中节点数的范围在 [0, 1 0 5 10^5 1 0 5 ] 内

    2024年02月06日
    浏览(44)
  • 【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :首先我们要知道后序遍历数组的最后一个元素必然是根节点,然后根据根节点在中序遍历数组中的位置进行划分,得到根节点的左右子树遍历数组,以此递归。当然这里有一个前提

    2024年02月10日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包