501. 二叉搜索树中的众数
题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/find-mode-in-binary-search-tree
题目
给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。
假定 BST 有如下定义:
- 结点左子树中所含结点的值小于等于当前结点的值
- 结点右子树中所含结点的值大于等于当前结点的值
- 左子树和右子树都是二叉搜索树
例如:
给定 BST [1,null,2,2],
1
2
/
2
返回 [2]
.
提示: 如果众数超过1个,不需考虑输出顺序
进阶: 你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)
解题思路
思路:中序遍历(递归)
先审题,题目给的是二叉搜索树(BST),关于 BST 的定义如下:
- 结点左子树中所含结点的值小于等于当前结点的值
- 结点右子树中所含结点的值大于等于当前结点的值
- 左子树和右子树都是二叉搜索树
根据 BST 的定义,我们可以发现,BST 中序遍历的输出结果是升序序列。在这道题中,BST 存在相同值。而最终的目的就是求出 BST 中的众数。
注意题目后面的提示,这里说明众数超过 1 个时,不考虑输出顺序。也就是说存在出现频率相同的元素。
这里我们来分析下,若已知一组升序序列,其中序列存在相同值。此时,若我们需要求得序列中的众数的做法大致如下(这里仅罗列大致思路,并非完整思路):
- 定义变量 ans 存储所求众数;
- 定义变量 count 存储元素出现的次数;
- 定义遍历 max_count,存储元素出现的最大次数;
- 对比 count、max_count,由此来判断哪个元素是否为众数;
- 遍历序列(因为序列有序),比较前后元素就能够判断元素是否相同,统计相同元素出现的次数,从而求得众数。
而这道题中,BST 中序遍历的输出结果是升序序列,那么上面的逻辑也是可以用在求 BST 众数。
中序遍历:处理节点值,是在递归左子树之后,递归右子树之前。
那么我们将上面求众数的逻辑,放到处理节点值这部分。具体代码如下(注释里补充相应逻辑)。
# 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内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复