给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。 如果树中有不止一个众数,可以按 任意顺序 返回。 假定 BST 满足如下定义: 结点左子树中所含节点的值 小于等于 当前节点的值 结点右子树中所含节点的值 大于等于 当前节点的值 左子树和右子树都是二叉搜索树
时间: 2023-02-06 20:54:28 浏览: 140
要找出二叉搜索树中的众数,我们可以考虑使用中序遍历的方法。在中序遍历中,每个节点的值都按升序排列,因此我们可以通过跟踪当前节点值出现的次数,找出当前出现次数最多的节点值。
我们可以使用一个哈希表来跟踪每个节点值出现的次数,然后在中序遍历的过程中更新哈希表。最后,我们可以遍历哈希表,找出所有出现次数最多的节点值并返回它们。
下面是一个 Python 代码的示例,它实现了上述算法:
```
def findMode(root):
if not root:
return []
# 使用哈希表跟踪每个节点值出现的次数
count = {}
def inorder(node):
if not node:
return
inorder(node.left)
count[node.val] = count.get(node.val, 0) + 1
inorder(node.right)
# 中序遍历树,更新哈希表
inorder(root)
# 找出所有出现次数最多的节点值
max_count = max(count.values())
return [val for val, cnt in count.items() if cnt == max_count]
```
上述代码中使用了递归的中序遍历算法。如果您希望使用迭代的方法,也可以使用堆栈来实现中序遍历。
希望这些信息对您有帮助。
阅读全文