代码随想录算法训练营第18天—二叉树07 | ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● *236. 二叉树的最近公共祖先

本文主要是介绍代码随想录算法训练营第18天—二叉树07 | ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● *236. 二叉树的最近公共祖先，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

题目链接/文章讲解：https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html
视频讲解：https://www.bilibili.com/video/BV1DD4y11779

• 考点
  • 二叉搜索树的性质
  • 中序遍历
• 我的思路
  • 先给Solution类初始化两个成员属性min_value和pre，分别存放最小差和当前节点的上一节点
  • 下面进行中序遍历，并利用双指针计算差值
  • 递归三要素
    • 形参：当前节点；返回值min_value
    • 退出条件：当前节点为None时，返回空
    • 递归逻辑
      • 左递归
      • 中间同时判断pre不为空和差值小于最小值，此时改变min_value
      • 把当前节点赋给pre
      • 右递归
      • 返回min_value
• 视频讲解关键点总结
  • 未看视频
• 我的思路的问题
  • 无
• 代码书写问题
  • 无
• 可执行代码

class Solution:def __init__(self):self.min_value = float('inf')self.pre = Nonedef getMinimumDifference(self, root: Optional[TreeNode]) -> int:if root is None:returnself.getMinimumDifference(root.left)if self.pre is not None and (root.val - self.pre.val) < self.min_value:self.min_value = root.val - self.pre.valself.pre = rootself.getMinimumDifference(root.right)return self.min_value

501.二叉搜索树中的众数

https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html
视频讲解：https://www.bilibili.com/video/BV1fD4y117gp

• 考点
  • 二叉搜索树的性质
• 我的思路
  • 先给Solution类初始化4个属性，结果列表、最大频率（初始化为1）、当前值频率（初始化为1）、当前节点的上一节点pre
  • 递归三要素
    • 形参：当前节点；返回值为结果列表
    • 退出条件：如果当前节点为None，返回空列表
    • 递归逻辑
      • 左递归
      • 如果pre不存在，把当前节点（根节点）的值加入结果列表
      • 如果pre存在且当前节点值与上一节点相同，当前频率加1
        • 如果当前频率>最大频率，令最大频率等于当前频率，并让结果列表等于仅包含当前节点值的新列表
        • 如果当前频率=最大频率，把当前节点值加入结果列表
      • 如果pre存在且当前节点值与上一节点不同，令当前频率重新归为1，此时需要额外判断最大频率是否为1，如果为1，说明目前已遍历过的节点均不重复，此时所有值都是众数，应该把当前值也加入结果列表
      • 令pre等于当前节点
      • 右递归
      • 返回结果列表
• 视频讲解关键点总结
  • 如果不是二叉搜索树，可以利用字典统计树中数值出现的频率，经过排序后输出结果
  • 二叉搜索树的思路和我一致
• 我的思路的问题
  • 因为是二叉搜索树，所以出现频率相同的时候数值不可能相同，因此在加入结果列表之前不需要判断当前值是否存在
• 代码书写问题
  • 无
• 可执行代码

class Solution:def __init__(self):self.result = []self.pre = Noneself.max_times = 1self.cur_times = 1def findMode(self, root: Optional[TreeNode]) -> List[int]:if root is None:return []self.findMode(root.left)if self.pre is not None and self.pre.val == root.val:self.cur_times += 1if self.cur_times > self.max_times:self.max_times = self.cur_timesself.result = [root.val]elif self.cur_times == self.max_times:self.result.append(root.val)elif self.pre is not None and self.pre.val != root.val:if self.max_times == 1:self.result.append(root.val)self.cur_times = 1elif self.pre is None:self.result.append(root.val)self.pre = rootself.findMode(root.right)return self.result

*236. 二叉树的最近公共祖先

https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html
视频讲解：https://www.bilibili.com/video/BV1jd4y1B7E2

• 考点
  • 从下向上处理（后序遍历）
• 我的思路
  • 想到了可能要用到递归+回溯，但是无具体思路
• 视频讲解关键点总结
  • 公共祖先的出现可能有两种情况，一种情况是两个节点分别在公共祖先的左右子树；另一种情况是公共祖先就是节点之一，另一节点在其左/右子树
  • 实际代码书写时，第一种情况包含了第二种情况
  • 递归三要素
    • 形参：两节点；返回值，最近公共祖先
    • 退出条件
      • 条件一，当前节点为None，返回None
      • 条件二，当前节点为所寻节点，返回当前节点
    • 递归逻辑
      • 左递归并接收返回值
      • 右递归并接收返回值
      • 如果左右返回值均不为None，则发生了情况一，此时直接返回当前节点即为最近公共祖先
      • 如果左右返回值一个为空一个不为空，则返回不为空的那个返回值
      • 如果均为空，返回None
  • 可以发现，如果发生了情况二，则当遇到最近公共祖先时，由于该节点也是目标节点之一，将直接满足退出条件发生返回，此时该节点将按照递归逻辑里的“如果左右返回值一个为空一个不为空，则返回不为空的那个返回值”一直返回，并成为最终的结果。因此，两种情况使用了同一份代码解决
• 我的思路的问题
  • 无思路
• 代码书写问题
  • 无
• 可执行代码

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if root is None:return Noneif root is p or root is q:return rootleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)if left and right:return rootelif left and not right:return leftelif not left and right:return rightelse:return None

这篇关于代码随想录算法训练营第18天—二叉树07 | ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● *236. 二叉树的最近公共祖先的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---