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

相关推荐
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.二叉搜索树的迭代
一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历。

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

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

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

视频讲解

这次搜索有方向了

重点分析

方法一：
递归法

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

方法二：
迭代法

def searchBST(root, val):current = rootwhile current:if current.val > val:current = current.leftcontinueif current.val < val:current = current.rightcontinueelse:breakreturn current

验证二叉搜索树

Key Points

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

视频讲解

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

重点分析

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

def checkBST(node, minVal, maxVal):if not node:return Trueif node.val <= minVal or node.val >= maxVal:return Falsereturn 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 Trueleft = self.isValidBST(root.left)if self.pre is not None and self.pre.val >= root.val:return Falseself.pre = root  # 记录前一个节点right = self.isValidBST(root.right)return left and right

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

在这里插入图片描述

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

二叉搜索树的最小绝对差

Key Points

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

视频讲解

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

重点分析

方法一：
递归法

class Solution(object):def __init__(self):self.pre = None   self.diff = float('inf')  # 只使用一次，所以是全局变量def getMinimumDifference(self, root):self.in_traversal(root)return self.diffdef in_traversal(self, root):if not root:returnself.in_traversal(root.left)if self.pre:self.diff = min(root.val - self.pre.val, self.diff)self.pre = rootself.in_traversal(root.right)return

方法二：
迭代法 + 暴力

def getMinimumDifference(root):stack_record = []current = rootres = []while stack_record or current:while current:stack_record.append(current)current = current.leftcurrent = stack_record.pop()res.append(current.val)# 左中都处理完了，转向右current = current.righti = 0j = i+1diff = res[j] - res[i]while j < len(res):diff = min(res[j] - res[i], diff)i += 1j += 1return diff

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

方法三：
迭代法+简化

def getMinimumDifference(root):stack_record = []current = rootdiff = float('inf')pre = Nonewhile stack_record or current:while current:stack_record.append(current)current = current.leftcurrent = stack_record.pop()if pre is None:   # if not pre 不行，警惕0的情况pre = current.valelse:diff = min(current.val-pre, diff)pre = current.valcurrent = current.rightreturn diff

二叉搜索树中的众数

Key Points

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

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

视频讲解

双指针+代码技巧

重点分析

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

def findMode(root):res = []stack_record = []current = rootwhile stack_record or current:while current:stack_record.append(current)current = current.leftcurrent = stack_record.pop()res.append(current.val)current = current.rightrecord = {}for x in res:record[x] = record.get(x, 0) + 1record_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:breakreturn results

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

def findMode(root):res = []stack_record = []current = rootwhile stack_record or current:while current:stack_record.append(current)current = current.leftcurrent = stack_record.pop()res.append(current.val)current = current.rightpre = Nonecount = 0max_count = 0results = []for x in res:if pre is not None:if pre == x:count +=1else:count = 1else:count = 1pre = xif count == max_count:results.append(x)elif count > max_count:max_count = countresults = [x]return results

方法三：
遍历一遍迭代法

def findMode(root):res = []pre = Nonemax_count = 0count = 0stack_record = []current = rootwhile stack_record or current:while current:stack_record.append(current)current = current.leftcurrent = stack_record.pop()if pre:if current.val == pre.val:count += 1else:count = 1else:count = 1pre = currentif count == max_count:res.append(current.val)elif count > max_count:max_count = countres = [current.val]current = current.rightreturn res

方法四：
遍历一遍递归法

class Solution:def __init__(self):self.pre = Noneself.res = []self.max_count = 0self.count = 0def in_traversal(self, root):if not root:returnself.in_traversal(root.left)if self.pre:if root.val == self.pre.val:self.count += 1else:self.count = 1else:self.count = 1self.pre = rootif self.count == self.max_count:self.res.append(root.val)elif self.count > self.max_count:self.max_count = self.countself.res = [root.val]self.in_traversal(root.right)returndef findMode(self, root):self.in_traversal(root)return self.res