一、二叉搜索树的最小绝对差（Leetcode 530）
思路1 ：中序遍历将二叉树转化为有序数组，然后暴力求解。
class Solution:
def __init__(self):
# 初始化一个空的列表，用于保存树的节点值
self.vec = []
def traversal(self, root):
# 递归函数进行中序遍历，填充self.vec列表
if root is None:
return # 如果当前节点为空，直接返回
# 先递归遍历左子树
self.traversal(root.left)
# 将当前节点的值添加到vec列表中
self.vec.append(root.val)
# 然后递归遍历右子树
self.traversal(root.right)
def getMinimumDifference(self, root):
# 清空self.vec，确保每次调用时都能重新计算最小差值
self.vec = []
# 中序遍历树，将节点值按升序存入self.vec
self.traversal(root)
# 如果树中少于两个节点，则没有有效的差值可计算，返回0
if len(self.vec) < 2:
return 0
# 初始化最小差值为正无穷大，用于后续的最小差值比较
result = float('inf')
# 遍历self.vec，计算相邻节点值之间的差值
for i in range(1, len(self.vec)):
# 计算相邻节点之间的差值，并更新最小差值
result = min(result, self.vec[i] - self.vec[i - 1])
# 返回最小差值
return result
思路2：双指针直接操作二叉树，求任意不同节点值的最小差。
class Solution:
def __init__(self):
# 初始化最小差值为正无穷，表示尚未计算差值
self.result = float('inf')
# 初始化pre为None，用来记录上一个访问的节点
self.pre = None
def traversal(self, cur):
# 如果当前节点为空，直接返回
if cur is None:
return
# 递归遍历左子树
self.traversal(cur.left)
# 计算当前节点与上一个节点的差值
if self.pre is not None: # 如果pre不为空，说明当前节点不是最左边的节点
# 更新最小差值，计算当前节点与前一个节点的差值，并更新result为更小的值
self.result = min(self.result, cur.val - self.pre.val)
# 记录当前节点，作为下一个节点的前一个节点
self.pre = cur
# 递归遍历右子树
self.traversal(cur.right)
def getMinimumDifference(self, root):
# 调用traversal进行中序遍历
self.traversal(root)
# 返回计算得到的最小差值
return self.result
二、二叉搜索树中的众数（Leetcode 501）
思路1：利用字典
from collections import defaultdict
# 定义二叉树节点类 TreeNode
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
# 在BST中搜索并统计每个节点的值的频率
def searchBST(self, cur, freq_map):
if cur is None:
return
# 统计当前节点值的频率
freq_map[cur.val] += 1
# 递归遍历左子树
self.searchBST(cur.left, freq_map)
# 递归遍历右子树
self.searchBST(cur.right, freq_map)
# 找出二叉搜索树中的出现频率最高的值
def findMode(self, root):
# 初始化一个字典来记录每个元素的频率，使用defaultdict方便处理未出现的键
freq_map = defaultdict(int)
result = []
# 如果根节点为空，返回空列表
if root is None:
return result
# 调用递归方法遍历二叉树并统计频率
self.searchBST(root, freq_map)
# 获取频率的最大值
max_freq = max(freq_map.values())
# 找出所有出现频率等于最大值的元素
for key, freq in freq_map.items():
if freq == max_freq:
result.append(key)
# 返回频率最高的值
return result
思路二：利用二叉树性质
class Solution:
def __init__(self):
self.maxCount = 0 # 最大频率
self.count = 0 # 当前频率
self.pre = None # 前一个节点
self.result = [] # 存储众数
# 用中序遍历BST，并统计节点值的频率
def searchBST(self, cur):
if cur is None:
return
# 递归遍历左子树
self.searchBST(cur.left) # 左
# 中
if self.pre is None: # 第一个节点，初始化频率为1
self.count = 1
elif self.pre.val == cur.val: # 当前节点与前一个节点值相同，增加频率
self.count += 1
else: # 当前节点与前一个节点值不同，重新计数为1
self.count = 1
# 更新前一个节点为当前节点
self.pre = cur # 更新前一个节点
# 如果当前节点的频率等于最大频率，将该节点值添加到结果列表
if self.count == self.maxCount:
self.result.append(cur.val)
# 如果当前节点的频率大于最大频率，更新最大频率，并清空结果列表，将当前节点值加入
if self.count > self.maxCount:
self.maxCount = self.count # 更新最大频率
self.result = [cur.val] # 清空结果列表并将当前节点值加入
# 递归遍历右子树
self.searchBST(cur.right) # 右
return
def findMode(self, root):
self.count = 0 # 重置频率
self.maxCount = 0 # 重置最大频率
self.pre = None # 重置前一个节点
self.result = [] # 清空结果列表
self.searchBST(root) # 调用searchBST进行遍历并统计
return self.result # 返回众数
三、二叉树的最近公共祖先（Leetcode 236）
class Solution:
# 定义一个函数来寻找最近公共祖先
def lowestCommonAncestor(self, root, p, q):
# 基本的终止条件
# 1. 如果当前节点是 p 或 q，返回当前节点。
# 2. 如果当前节点是 None，说明这条路径不包含 p 或 q，返回 None。
if root == q or root == p or root is None:
return root
# 递归遍历左子树，找到 p 和 q 中其中一个的最近公共祖先
left = self.lowestCommonAncestor(root.left, p, q)
# 递归遍历右子树，找到 p 和 q 中其中一个的最近公共祖先
right = self.lowestCommonAncestor(root.right, p, q)
# 如果左子树和右子树分别都找到了 p 或 q，说明当前节点是最近公共祖先
# 因为 p 和 q 分别位于左右子树
if left is not None and right is not None:
return root
# 如果左子树找到了 p 或 q，右子树为 None，说明公共祖先在左子树
if left is None and right is not None:
return right
# 如果右子树找到了 p 或 q，左子树为 None，说明公共祖先在右子树
elif left is not None and right is None:
return left
# 如果左右子树都为 None，说明当前节点不是公共祖先，返回 None
else:
return None