LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】

简介: LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

python源码解读

程序员必备的数学知识与应用

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

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

输入格式
  • root:二叉树的根节点。
输出格式
  • 不需要返回值,直接在原树上进行恢复。

示例

示例 1
输入: [1,3,null,null,2]
输出: [3,1,null,null,2]
解释: 3 和 1 被错误交换。
示例 2
输入: [3,1,4,null,null,2]
输出: [2,1,4,null,null,3]
解释: 2 和 3 被错误交换。

方法一:中序遍历和交换

解题步骤
  1. 中序遍历:使用中序遍历找到两个错误的节点。
  2. 节点交换:找到两个不符合中序递增顺序的节点后,交换它们的值。
完整的规范代码
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def recoverTree(root):
    """
    使用中序遍历恢复二叉搜索树
    :param root: TreeNode, 二叉搜索树的根节点
    """
    stack = []
    x = y = prev = None
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        if prev and root.val < prev.val:
            y = root
            if not x:
                x = prev
            else:
                break
        prev = root
        root = root.right
    # 交换两个节点的值
    if x and y:
        x.val, y.val = y.val, x.val
# 示例调用
root = TreeNode(1, TreeNode(3, None, TreeNode(2)))
recoverTree(root)
算法分析
  • 时间复杂度:(O(n)),需要遍历所有节点。
  • 空间复杂度:(O(h)),其中 (h) 是树的高度,用于存储栈。
中序遍历的 ASCII 图解

假设我们有一个二叉树,其中两个节点值被错误交换,例如树结构为:

3
   / \
  1   4
     /
    2

中序遍历应为 [1, 3, 4, 2],但正确的排序应为 [1, 2, 3, 4],其中 4 和 2 被错误地交换。

开始中序遍历:
    访问节点 3
    |   去左 -> 访问节点 1
    |   |   打印节点 1
    |   |   返回节点 3
    |   打印节点 3
    |   去右 -> 访问节点 4
    |   |   去左 -> 访问节点 2
    |   |   |   打印节点 2
    |   |   |   返回节点 4
    |   |   打印节点 4
    |   |   结束

方法二:Morris 中序遍历

解题步骤
  1. Morris 遍历:这种遍历方式不需要额外的空间,通过修改树的结构实现。
  2. 找出并交换错误节点:在遍历过程中寻找顺序错误的节点,并在遍历结束后交换它们的值。
完整的规范代码
def recoverTree(root):
    x = y = prev = pred = None
    while root:
        if root.left:
            pred = root.left
            while pred.right and pred.right != root:
                pred = pred.right
            if not pred.right:
                pred.right = root
                root = root.left
            else:
                if prev and root.val < prev.val:
                    y = root
                    if not x:
                        x = prev
                prev = root
                pred.right = None
                root = root.right
        else:
            if prev and root.val < prev.val:
                y = root
                if not x:
                    x = prev
            prev = root
            root = root.right
    if x and y:
        x.val, y.val = y.val, x.val
# 示例调用
root = TreeNode(1, TreeNode(3, None, TreeNode(2)))
recoverTree(root)
算法分析
  • 时间复杂度:(O(n)),虽然是 Morris 遍历,每个节点最多被访问两次。
  • 空间复杂度:(O(1)),不使用额外空间,除非修改了树的结构。

不同算法的优劣势对比

特征 方法一:中序遍历 方法二:Morris 遍历
时间复杂度 (O(n)) (O(n))
空间复杂度 (O(h)) (O(1))
优势 易于理解和实现 不需要额外空间
劣势 空间复杂度较高 修改了树的结构
Morris 遍历的 ASCII 图解

使用同样的树结构进行 Morris 遍历,我们通过修改树的结构来避免使用额外的空间。

开始Morris遍历:
    访问节点 3
    |   左节点存在,找到前驱(节点 1)
    |   |   前驱的右节点为空,链接到当前节点
    |   |   去左
    |   访问节点 1
    |   |   前驱是节点 3,断开链接,打印节点 1
    |   |   返回节点 3,打印节点 3
    |   去右 -> 访问节点 4
    |   |   左节点存在,找到前驱(节点 2)
    |   |   |   前驱的右节点为空,链接到当前节点
    |   |   |   去左
    |   |   访问节点 2
    |   |   |   前驱是节点 4,断开链接,打印节点 2
    |   |   |   返回节点 4,打印节点 4
    |   |   结束

应用示例

这些方法可用于数据库中维护数据索引的完整性、修复由于错误操作或系统故障导致数据结构损坏的情况,或者在进行复杂的数据操作前验证数据的一致性。

欢迎关注微信公众号 数据分析螺丝钉


相关文章
|
26天前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
11 1
|
1月前
|
存储 算法 Python
python常用算法(5)——树,二叉树与AVL树(一)
python常用算法(5)——树,二叉树与AVL树
|
11天前
|
Python
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
|
11天前
|
存储 算法 索引
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
|
11天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
存储 算法 调度
力扣中级算法(Python)
力扣中级算法(Python)
|
1月前
|
算法 Python
力扣初级算法(Python)(二)
力扣初级算法(Python)(二)
|
1月前
二刷力扣--二叉树(1)基础、遍历
二刷力扣--二叉树(1)基础、遍历
|
1月前
|
算法 Python
力扣初级算法(Python)(一)
力扣初级算法(Python)(一)
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素