我是靠谱客的博主 负责柠檬,这篇文章主要介绍LeetCode 501. 二叉搜索树中的众数 | Python501. 二叉搜索树中的众数,现在分享给大家,希望可以做个参考。

501. 二叉搜索树中的众数


题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/find-mode-in-binary-search-tree

题目


给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。

假定 BST 有如下定义:

  • 结点左子树中所含结点的值小于等于当前结点的值
  • 结点右子树中所含结点的值大于等于当前结点的值
  • 左子树和右子树都是二叉搜索树

例如:

给定 BST [1,null,2,2],

复制代码
1
2
3
4
5
6
1 2 / 2

返回 [2].

提示: 如果众数超过1个,不需考虑输出顺序

进阶: 你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)

解题思路


思路:中序遍历(递归)

先审题,题目给的是二叉搜索树(BST),关于 BST 的定义如下:

  • 结点左子树中所含结点的值小于等于当前结点的值
  • 结点右子树中所含结点的值大于等于当前结点的值
  • 左子树和右子树都是二叉搜索树

根据 BST 的定义,我们可以发现,BST 中序遍历的输出结果是升序序列。在这道题中,BST 存在相同值。而最终的目的就是求出 BST 中的众数。

注意题目后面的提示,这里说明众数超过 1 个时,不考虑输出顺序。也就是说存在出现频率相同的元素。

这里我们来分析下,若已知一组升序序列,其中序列存在相同值。此时,若我们需要求得序列中的众数的做法大致如下(这里仅罗列大致思路,并非完整思路):

  • 定义变量 ans 存储所求众数;
  • 定义变量 count 存储元素出现的次数;
  • 定义遍历 max_count,存储元素出现的最大次数;
  • 对比 count、max_count,由此来判断哪个元素是否为众数;
  • 遍历序列(因为序列有序),比较前后元素就能够判断元素是否相同,统计相同元素出现的次数,从而求得众数。

而这道题中,BST 中序遍历的输出结果是升序序列,那么上面的逻辑也是可以用在求 BST 众数。

中序遍历:处理节点值,是在递归左子树之后,递归右子树之前。

那么我们将上面求众数的逻辑,放到处理节点值这部分。具体代码如下(注释里补充相应逻辑)。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def findMode(self, root: TreeNode) -> List[int]: ans = [] count = 0 max_count = 0 # 这里用以比对遍历的节点前后值是否相同 # 初始化为 None pre = None def handle_node(node): nonlocal ans, count, max_count, pre # pre 初始为 None,若无变化,表示当前节点是第一个节点 # 注意更新 pre if not pre: count = 1 pre = node # 比较 pre 与当前节点 node # 相同,则更新 count elif pre.val == node.val: count += 1 # 不同,则表示元素发生变化,重新初始化 count else: count = 1 pre = node # 如果出现 count == max_count 的情况,表示出现频率相同的元素 # 放到 ans 列表中 if count == max_count: ans.append(node.val) # 如果 count > max_count 时,表示元素频率出现新的大值 # 更新 max_count,同时更新 ans if count > max_count: max_count = count ans = [node.val] def inorder(root): if not root: return # 递归左子树 inorder(root.left) # 处理节点值 handle_node(root) # 递归右子树 inorder(root.right) inorder(root) return ans

欢迎关注


公众号 【书所集录】

最后

以上就是负责柠檬最近收集整理的关于LeetCode 501. 二叉搜索树中的众数 | Python501. 二叉搜索树中的众数的全部内容,更多相关LeetCode内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(58)

评论列表共有 0 条评论

立即
投稿
返回
顶部