0501：二叉搜索树中的众数

力扣第 501 题

题目

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

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

示例 1：

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

示例 2：

输入：root = [0]
输出：[0]

提示：

• 树中节点的数目在范围 [1, 104] 内
• -105 <= Node.val <= 105

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

分析

最简单的就是遍历得到数组，再求众数。

要求不用额外空间，可以按中序遍历，相同元素必然相邻，因此维护当前元素的频次，更新结果即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def findMode(self, root: TreeNode) -> List[int]:
	res, maxcnt = [], 0
	stack, pre, cnt = [root], None, 0
	while stack:
		node = stack.pop()
		if isinstance(node, int):
			cnt, pre = cnt*(node==pre)+1, node
			if cnt >= maxcnt:
				res, maxcnt = res*(cnt==maxcnt)+[node], cnt
		elif node:
			stack.extend([node.right, node.val, node.left])
	return res

76 ms