代码随想录训练营 Day18打卡 二叉树 part06

一、 力扣530. 二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 ：
输入： root = [4,2,6,1,3]
输出： 1

我们需要用一个pre节点记录一下cur节点的前一个节点。如图：

版本一 递归法

首先将二叉搜索树的所有节点值转换为一个有序数组，然后计算数组中连续元素的最小差值。

class Solution:def __init__(self):self.vec = []  # 存储中序遍历结果的数组def traversal(self, root):"""中序遍历二叉搜索树，保证遍历结果的数组是有序的。"""if root is None:returnself.traversal(root.left)  # 访问左子树self.vec.append(root.val)  # 将节点值加入数组self.traversal(root.right)  # 访问右子树def getMinimumDifference(self, root):"""计算二叉搜索树中任意两个不同节点值之间的最小差值。"""self.vec = []  # 重置数组self.traversal(root)  # 执行中序遍历if len(self.vec) < 2:return 0  # 如果数组中的元素少于2个，直接返回0result = float('inf')for i in range(1, len(self.vec)):result = min(result, self.vec[i] - self.vec[i - 1])  # 计算相邻元素之间的最小差值return result

版本二 递归法

直接在中序遍历过程中计算最小差值，避免了使用额外的数组存储。

class Solution:def __init__(self):self.result = float('inf')  # 初始化最小差值为无穷大self.pre = None  # 用于存储上一个访问的节点def traversal(self, cur):"""递归中序遍历并更新最小差值。"""if cur is None:returnself.traversal(cur.left)if self.pre is not None:self.result = min(self.result, cur.val - self.pre.val)  # 更新最小差值self.pre = cur  # 更新前一个节点self.traversal(cur.right)def getMinimumDifference(self, root):self.traversal(root)return self.result

版本三 迭代法

使用迭代的方式执行中序遍历，并在遍历过程中计算最小差值。

class Solution:def getMinimumDifference(self, root):stack = []  # 使用栈来管理迭代过程中的节点cur = root  # 当前访问的节点pre = None  # 上一个访问的节点result = float('inf')  # 初始化最小差值为无穷大while cur is not None or len(stack) > 0:if cur is not None:stack.append(cur)  # 将当前节点加入栈中cur = cur.left  # 移至左子节点else:cur = stack.pop()  # 从栈中取出节点进行处理if pre is not None:result = min(result, cur.val - pre.val)  # 更新最小差值pre = cur  # 更新前一个节点cur = cur.right  # 移至右子节点return result

力扣题目链接
题目文章讲解
题目视频讲解

二、 力扣501. 二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
    结点左子树中所含节点的值 小于等于 当前节点的值
    结点右子树中所含节点的值 大于等于 当前节点的值
    左子树和右子树都是二叉搜索树
示例 ：

输入： root = [1,null,2,2]
输出： [2]

版本一 递归法：利用字典

使用字典来存储每个元素的出现次数，并通过遍历字典来确定哪些元素的出现频率最高。

from collections import defaultdictclass Solution:def searchBST(self, cur, freq_map):"""递归遍历树并统计每个值的出现次数。参数：- 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):"""找出BST中的众数。返回具有最高频率的元素列表。"""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

版本二 递归法：利用二叉搜索树性质

详细思路

1. 初始化状态变量：

   self.maxCount: 用来记录遍历过程中遇到的最大的元素频率。
   self.count: 用于记录当前遍历的元素的连续出现次数。
   self.pre: 指向上一个访问的节点，用于比较当前节点和上一个节点的值。
   self.result: 用来存储频率最高的元素列表。

2. 中序遍历实现：

        使用递归方法进行中序遍历，这意味着首先处理左子树，然后处理当前节点，最后处理右子树。
        在处理当前节点之前，左子树的所有元素已经被处理，这保证了元素的访问顺序是从小到大。

3. 计算元素频率：

   当遍历到一个新节点时，首先检查它是否与前一个节点的值相同。
   如果与前一个节点值相同，则增加self.count的值。
   如果不同，说明遇到了一个新的元素，因此需要重置self.count为1。

4. 更新众数和频率记录：

   在每次更新self.count后，比较self.count和self.maxCount。
   如果self.count大于self.maxCount，这意味着找到了一个更频繁的元素，因此更新self.maxCount为新的self.count，并且重置self.result为仅包含当前节点的值。
   如果self.count等于self.maxCount，将当前节点的值添加到self.result中，因为它的出现频率与目前已知的最高频率相同。

5. 递归的连续性：

   继续递归调用处理右子树，保持中序遍历的连续性。
   遍历完成后，所有元素都被按照上述逻辑处理过，self.result将包含所有的众数。

6. 返回结果：

   完成整棵树的遍历后，self.result中存储的就是所有出现频率最高的元素。
   返回self.result作为函数的输出。

class Solution:def __init__(self):self.maxCount = 0  # 记录最大频率self.count = 0  # 当前遍历元素的计数self.pre = None  # 前一个节点self.result = []  # 存储结果的列表def searchBST(self, cur):"""递归遍历BST，同时计算众数。使用中序遍历保证元素从小到大访问。"""if cur is None:returnself.searchBST(cur.left)if self.pre is None or self.pre.val != cur.val:self.count = 1  # 如果当前元素与前一个元素不同，则重置计数器else:self.count += 1  # 否则增加计数器if self.count > self.maxCount:  # 如果当前元素计数超过之前的最大频率self.maxCount = self.count  # 更新最大频率self.result = [cur.val]  # 重置结果列表为当前元素elif self.count == self.maxCount:self.result.append(cur.val)  # 如果当前元素频率等于最大频率，加入结果列表self.pre = cur  # 更新前一个节点为当前节点self.searchBST(cur.right)def findMode(self, root):self.searchBST(root)return self.result

版本三 迭代法

使用栈实现中序遍历的迭代方式，同时在遍历过程中更新众数的计数。

class Solution:def findMode(self, root):"""使用栈实现的迭代中序遍历，找出BST中的众数。返回具有最高频率的元素列表。"""st = []  # 栈用于存储节点，实现迭代中序遍历cur = rootpre = None  # 前一个节点maxCount = 0  # 最大频率count = 0  # 当前元素频率计数result = []  # 结果列表while cur is not None or st:while cur is not None:  # 移动到最左边st.append(cur)  # 将节点压入栈cur = cur.leftcur = st.pop()  # 从栈中取出节点if pre is None or pre.val != cur.val:count = 1  # 重置计数器else:count += 1  # 增加计数器if count > maxCount:maxCount = count  # 更新最大频率result = [cur.val]  # 重置结果列表elif count == maxCount:result.append(cur.val)  # 如果当前频率与最大频率相同，加入结果列表pre = cur  # 更新前一个节点cur = cur.right  # 移动到右子节点return result

力扣题目链接
题目文章讲解
题目视频讲解

三、 力扣236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 ：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。
即情况一：

但很多人容易忽略一个情况，就是节点本身p(q)，它拥有一个子孙节点q§。 情况二：

其实情况一 和 情况二 代码实现过程都是一样的，也可以说，实现情况一的逻辑，顺便包含了情况二。

因为遇到 q 或者 p 就返回，这样也包含了 q 或者 p 本身就是 公共祖先的情况。

递归三部曲

1. 确定递归函数的返回值和参数:

   参数：当前节点 root，节点 p 和 q。
   返回值：树中节点 p 和 q 的最低公共祖先。

2. 确定终止条件:

   如果当前节点为空，返回 None。
   如果当前节点等于 p 或 q，返回当前节点。

3. 确定单层递归逻辑:

   对当前节点的左子树和右子树分别进行递归。
   根据左右子树的返回值判断当前节点是否是 p 和 q 的最低公共祖先：
       如果左右子树递归结果都非空，返回当前节点。
       如果其中一侧为空，返回非空的一侧。
       如果两侧都为空，返回 None。

版本一 递归法

这个版本是典型的递归解法，利用了分治的思想来找到二叉树中两个节点（p 和 q）的最低公共祖先（LCA）。

class Solution:def lowestCommonAncestor(self, root, p, q):# 如果当前节点为空，或者等于p或q，则返回当前节点if root is None or root == p or root == q:return root# 递归查找左子树中的最低公共祖先left = self.lowestCommonAncestor(root.left, p, q)# 递归查找右子树中的最低公共祖先right = self.lowestCommonAncestor(root.right, p, q)# 如果左右子树的递归调用都返回了非空节点，说明p和q在root的两侧，root就是LCAif left is not None and right is not None:return root# 如果只有右子树递归返回非空，说明LCA在右子树if left is None and right is not None:return right# 如果只有左子树递归返回非空，说明LCA在左子树elif left is not None and right is None:return left# 如果左右子树递归都返回空，说明当前子树中没有p和q，返回Noneelse:return None

版本二 递归法 精简

这个版本精简了代码，去掉了一些冗余的条件判断，使逻辑更直接。

class Solution:def lowestCommonAncestor(self, root, p, q):# 如果当前节点为空，或者等于p或q，则返回当前节点if root is None or root == p or root == q:return root# 递归查找左子树中的最低公共祖先left = self.lowestCommonAncestor(root.left, p, q)# 递归查找右子树中的最低公共祖先right = self.lowestCommonAncestor(root.right, p, q)# 如果左右子树的递归调用都返回了非空节点，说明p和q在root的两侧，root就是LCAif left is not None and right is not None:return root# 如果左子树为空，返回右子树的结果；否则返回左子树的结果return right if left is None else left

力扣题目链接
题目文章讲解
题目视频讲解