一、二叉搜索樹的最小絕對差（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.vecself.traversal(root)# 如果樹中少于兩個節點，則沒有有效的差值可計算，返回0if 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 = Nonedef 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 = rightclass 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:  # 第一個節點，初始化頻率為1self.count = 1elif self.pre.val == cur.val:  # 當前節點與前一個節點值相同，增加頻率self.count += 1else:  # 當前節點與前一個節點值不同，重新計數為1self.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)  # 右returndef 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，說明當前節點不是公共祖先，返回 Noneelse:return None