当前位置： 首页 > article >正文

python coding with ChatGPT 打卡第20天| 二叉搜索树：搜索、验证、最小绝对差、众数

article 2024/9/17 3:38:38

相关推荐
python coding with ChatGPT 打卡第12天| 二叉树：理论基础
python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历
python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历
python coding with ChatGPT 打卡第15天| 二叉树：翻转二叉树、对称二叉树
python coding with ChatGPT 打卡第16天| 二叉树：完全二叉树、平衡二叉树、二叉树的所有路径、左叶子之和
python coding with ChatGPT 打卡第17天| 二叉树：找树左下角的值、路径总和
python coding with ChatGPT 打卡第18天| 二叉树：从中序与后序遍历序列构造二叉树、最大二叉树
python coding with ChatGPT 打卡第19天| 二叉树：合并二叉树

二叉搜索树中的搜索

Key Points

1.二叉搜索树是一个有序树：

- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉搜索树

2.二叉搜索树的迭代
一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历。

对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。

对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支。

而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。

相关题目

700. 二叉搜索树中的搜索

视频讲解

这次搜索有方向了

重点分析

方法一：
递归法

def searchBST(root, val):
    if not root:
        return None
    if root.val > val:
        return searchBST(root.left, val)
    if root.val < val:
        return searchBST(root.right, val)
    return root

方法二：
迭代法

def searchBST(root, val):
    current = root
    while current:
        if current.val > val:
                current = current.left
                continue
        if current.val < val:
                current = current.right
                continue
        else:
            break
    return current

验证二叉搜索树

Key Points

在中序遍历下，输出的二叉搜索树节点的数值是升序序列。

相关题目

98. 验证二叉搜索树

视频讲解

你对二叉搜索树的了解还不够

重点分析

方法一：
不使用有序序列
在这里插入图片描述
我们可以定义一个辅助函数checkBST，它接收四个参数：当前节点node、minVal（当前节点值允许的最小值）、maxVal（当前节点值允许的最大值）、以及初始的根节点root。这个辅助函数将帮助我们递归地验证每个子树，同时保持跟踪允许的值的范围。

def checkBST(node, minVal, maxVal):
    if not node:
        return True
    if node.val <= minVal or node.val >= maxVal:
        return False
    return checkBST(node.left, minVal, node.val) and checkBST(node.right, node.val, maxVal)

def isValidBST(root):
    return checkBST(root, float('-inf'), float('inf'))

这段代码使用了一个嵌套的辅助函数checkBST来递归地验证每个节点是否符合二叉搜索树的条件，它通过维护每个节点的值允许的最小值和最大值来实现。这种方法能够确保所有的左子树节点都小于它的父节点，并且所有的右子树节点都大于它的父节点，同时还考虑了所有祖先节点的约束条件。

方法二：
使用有序序列 + 双指针 递归法
在这里插入图片描述

class Solution:
    def __init__(self):
        self.pre = None  # 用来记录前一个节点

    def isValidBST(self, root):
        if root is None:
            return True

        left = self.isValidBST(root.left)

        if self.pre is not None and self.pre.val >= root.val:
            return False
        self.pre = root  # 记录前一个节点

        right = self.isValidBST(root.right)
        return left and right

方法三：
使用有序序列 + 双指针 迭代法

在这里插入图片描述

def isValidBST(root):
    stack = []
    prev = None
    
    while stack or root:
        # 遍历到最左
        while root:
            stack.append(root)
            root = root.left
        
        # 访问节点
        root = stack.pop()
        
        # 检查当前节点是否大于前一个节点
        if prev and root.val <= prev.val:
            return False
        prev = root
        
        # 转向右子树
        root = root.right
    
    return True

二叉搜索树的最小绝对差

Key Points

  1. 在升序数组中，任意两个相邻元素的差值最小
  2. 1）暴力法：先中序遍历得到升序数列，再遍历数组求最小差值；
    2）简化法：遍历的过程中使用双指针

相关题目

530. 二叉搜索树的最小绝对差

视频讲解

二叉搜索树中的双指针遍历

重点分析

方法一：
递归法

class Solution(object):
    def __init__(self):
        self.pre = None   
        self.diff = float('inf')  # 只使用一次，所以是全局变量
        
    def getMinimumDifference(self, root):
        self.in_traversal(root)
        return self.diff

    def in_traversal(self, root):
        if not root:
            return
        self.in_traversal(root.left)
        if self.pre:
            self.diff = min(root.val - self.pre.val, self.diff)
        self.pre = root
        self.in_traversal(root.right)
        return

方法二：
迭代法 + 暴力

def getMinimumDifference(root):
    stack_record = []
    current = root
    res = []
    while stack_record or current:
        while current:
            stack_record.append(current)
            current = current.left

        current = stack_record.pop()
        res.append(current.val)

        # 左中都处理完了，转向右
        current = current.right

    i = 0
    j = i+1
    diff = res[j] - res[i]
    while j < len(res):
        diff = min(res[j] - res[i], diff)
        i += 1
        j += 1
    return diff

注：LeetCode题目中说明节点至少为两个，所以使用双指针不用讨论数组长度

方法三：
迭代法+简化

def getMinimumDifference(root):
    stack_record = []
    current = root
    diff = float('inf')
    pre = None
    while stack_record or current:
        while current:
            stack_record.append(current)
            current = current.left

        current = stack_record.pop()
        if pre is None:   # if not pre 不行，警惕0的情况
            pre = current.val
        else:
            diff = min(current.val-pre, diff)
            pre = current.val

        current = current.right

    return diff

二叉搜索树中的众数

Key Points

首先如果不是二叉搜索树的话，应该怎么解题，是二叉搜索树，又应该如何解题，两种方式做一个比较，可以加深大家对二叉树的理解。

  1. 如果不是二叉搜索树，最直观的方法一定是把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合。
  2. 对于二叉搜索树，遍历有序数组的元素出现频率，从头遍历，那么一定是相邻两个元素作比较，然后就把出现频率最高的元素输出就可以了。

相关题目

501. 二叉搜索树中的众数

视频讲解

双指针+代码技巧

重点分析

方法一：
暴力法 哈希表（迭代）

def findMode(root):
    res = []
    stack_record = []
    current = root

    while stack_record or current:
        while current:
            stack_record.append(current)
            current = current.left

        current = stack_record.pop()
        res.append(current.val)

        current = current.right

    record = {}
    for x in res:
        record[x] = record.get(x, 0) + 1

    record_sort = sorted(record.items(), key=lambda x:x[1], reverse=True)
    results = []
    max_val = record_sort[0][1]
    for x in record_sort:
        if x[1] == max_val:
            results.append(x[0])
        else:
            break

    return results

方法二：
遍历两遍 双指针 （迭代法）

def findMode(root):
    res = []
    stack_record = []
    current = root

    while stack_record or current:
        while current:
            stack_record.append(current)
            current = current.left

        current = stack_record.pop()
        res.append(current.val)

        current = current.right


    pre = None
    count = 0
    max_count = 0
    results = []

    for x in res:
        if pre is not None:
            if pre == x:
                count +=1
            else:
                count = 1
        else:
            count = 1
        pre = x
        if count == max_count:
            results.append(x)
        elif count > max_count:
            max_count = count
            results = [x]
    return results

方法三：
遍历一遍 迭代法

def findMode(root):
    res = []
    pre = None
    max_count = 0
    count = 0
    stack_record = []
    current = root

    while stack_record or current:
        while current:
            stack_record.append(current)
            current = current.left

        current = stack_record.pop()
        if pre:
            if current.val == pre.val:
                count += 1
            else:
                count = 1
        else:
            count = 1
        pre = current
        if count == max_count:
            res.append(current.val)
        elif count > max_count:
            max_count = count
            res = [current.val]

        current = current.right
    return res

方法四：
遍历一遍 递归法

class Solution:

    def __init__(self):
        self.pre = None
        self.res = []
        self.max_count = 0
        self.count = 0

    def in_traversal(self, root):
        if not root:
            return

        self.in_traversal(root.left)
        if self.pre:
            if root.val == self.pre.val:
                self.count += 1
            else:
                self.count = 1
        else:
            self.count = 1
        self.pre = root
        if self.count == self.max_count:
            self.res.append(root.val)
        elif self.count > self.max_count:
            self.max_count = self.count
            self.res = [root.val]

        self.in_traversal(root.right)
        return

    def findMode(self, root):
        self.in_traversal(root)
        return self.res

http://www.kler.cn/news/235002.html

相关文章：

  • GPT-4模型的创造力
  • 蓝桥杯备赛Day9——链表进阶
  • Ps：直接从图层生成文件（图像资源）
  • 《CSS 简易速速上手小册》第10章：未来的 CSS（2024 最新版）
  • 【MySQL】-21 MySQL综合-8（MySQL默认值+MySQL非空约束+MySQL查看表中的约束）
  • Ainx-V0.2-简单的连接封装与业务绑定
  • Could not connect to Redis at 127.0.0.1:6379:由于目标计算机积极拒绝，无法连接...问题解决方法之一
  • leaflet 显示自己geoserver发布的中国地图
  • WordPress修改所有用户名并发送邮件通知的插件Easy Username Updater
  • vue双向绑定的原理
  • CTF-PWN-沙箱逃脱-【侧信道爆破】（2021-蓝帽杯初赛-slient）
  • 【开源】基于JAVA+Vue+SpringBoot的实验室耗材管理系统
  • ERROR: Could not build wheels for roslz4
  • PMP-情景模拟学习法-识别时间点
  • 2.11作业
  • 图灵日记--MapSet字符串常量池反射枚举Lambda表达式泛型
  • Pandas数据预处理之数据标准化-提升机器学习模型性能的关键步骤【第64篇—python：数据预处理】
  • 深入探索Flex布局：从基础到实战，附带抖音解决方案案例分析
  • C++提高编程（黑马笔记）
  • Jedis
  • HarmonyOS 横屏调试与真机横屏运行
  • Spring Boot生成二维码的两种实现方式
  • 使用 Windows 11/10 上的最佳 PDF 转 Word 转换器释放 PDF 的潜力
  • 没更新的日子也在努力呀，布局2024！
  • sql常用函数积累（非窗口函数）
  • 从MySQL到TiDB：兼容性全解析
  • Linux(Ubuntu) 环境搭建：MySQL
  • Python中使用opencv-python进行人脸检测
  • Conda历史版本下载地址和python对应关系
  • 73. 矩阵置零（Java）