LeetCode 501: Find Mode in Binary Search Tree (Inorder Run-Length Counting)
LeetCode 501BSTInorderToday we solve LeetCode 501 - Find Mode in Binary Search Tree.
Source: https://leetcode.com/problems/find-mode-in-binary-search-tree/
English
Problem Summary
Given a BST root, return all values (in any order) that appear most frequently. The BST property makes inorder traversal produce a non-decreasing sequence, so equal values appear consecutively.
Key Insight
In inorder order, duplicates become one contiguous run. Track prevVal, current run length curCount, and global best maxCount. Whenever a run ends/extends, compare curCount with maxCount and update answer list accordingly.
Algorithm
- Inorder traverse BST (left, node, right).
- For each value:
• If equal to previous value, increment curCount; otherwise reset to 1.
• If curCount > maxCount, clear answer and add this value.
• If curCount == maxCount, append this value.
- Convert answer list to int array and return.
Complexity Analysis
Time: O(n).
Space: O(h) recursion stack (worst O(n), balanced O(log n)), excluding output.
Common Pitfalls
- Forgetting that there can be multiple modes.
- Not resetting curCount when value changes.
- Updating mode list only after run ends (you should update at each visit).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private Integer prev = null;
private int curCount = 0;
private int maxCount = 0;
private List<Integer> modes = new ArrayList<>();
public int[] findMode(TreeNode root) {
inorder(root);
int[] ans = new int[modes.size()];
for (int i = 0; i < modes.size(); i++) {
ans[i] = modes.get(i);
}
return ans;
}
private void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
handle(node.val);
inorder(node.right);
}
private void handle(int v) {
if (prev != null && prev == v) {
curCount++;
} else {
curCount = 1;
}
if (curCount > maxCount) {
maxCount = curCount;
modes.clear();
modes.add(v);
} else if (curCount == maxCount) {
modes.add(v);
}
prev = v;
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findMode(root *TreeNode) []int {
var prev *int
curCount, maxCount := 0, 0
modes := []int{}
var handle func(int)
handle = func(v int) {
if prev != nil && *prev == v {
curCount++
} else {
curCount = 1
}
if curCount > maxCount {
maxCount = curCount
modes = []int{v}
} else if curCount == maxCount {
modes = append(modes, v)
}
x := v
prev = &x
}
var inorder func(*TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left)
handle(node.Val)
inorder(node.Right)
}
inorder(root)
return modes
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int curCount = 0;
int maxCount = 0;
TreeNode* prev = nullptr;
vector<int> modes;
vector<int> findMode(TreeNode* root) {
inorder(root);
return modes;
}
void inorder(TreeNode* node) {
if (!node) return;
inorder(node->left);
handle(node);
inorder(node->right);
}
void handle(TreeNode* node) {
if (prev && prev->val == node->val) {
curCount++;
} else {
curCount = 1;
}
if (curCount > maxCount) {
maxCount = curCount;
modes.clear();
modes.push_back(node->val);
} else if (curCount == maxCount) {
modes.push_back(node->val);
}
prev = node;
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
self.prev = None
self.cur_count = 0
self.max_count = 0
self.modes = []
def handle(v: int) -> None:
if self.prev is not None and self.prev == v:
self.cur_count += 1
else:
self.cur_count = 1
if self.cur_count > self.max_count:
self.max_count = self.cur_count
self.modes = [v]
elif self.cur_count == self.max_count:
self.modes.append(v)
self.prev = v
def inorder(node: Optional[TreeNode]) -> None:
if not node:
return
inorder(node.left)
handle(node.val)
inorder(node.right)
inorder(root)
return self.modes/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var findMode = function(root) {
let prev = null;
let curCount = 0;
let maxCount = 0;
const modes = [];
const handle = (v) => {
if (prev !== null && prev === v) {
curCount++;
} else {
curCount = 1;
}
if (curCount > maxCount) {
maxCount = curCount;
modes.length = 0;
modes.push(v);
} else if (curCount === maxCount) {
modes.push(v);
}
prev = v;
};
const inorder = (node) => {
if (!node) return;
inorder(node.left);
handle(node.val);
inorder(node.right);
};
inorder(root);
return modes;
};中文
题目概述
给定一棵二叉搜索树，返回出现频率最高的所有元素（顺序任意）。由于 BST 的中序遍历结果是非递减序列，相同值会连续出现。
核心思路
中序遍历时，相同值会形成“连续段”。维护上一个值 prevVal、当前连续计数 curCount、历史最大频次 maxCount。每访问一个节点就更新计数，并根据与 maxCount 的关系刷新答案列表。
算法步骤
- 对 BST 做中序遍历（左-根-右）。
- 处理当前值时：
• 若与上一个值相同，curCount++；否则重置为 1。
• 若 curCount > maxCount，清空答案并加入当前值。
• 若 curCount == maxCount，将当前值追加进答案。
- 最后返回答案数组。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(h)（递归栈，最坏 O(n)，平衡树约 O(log n)），不含输出数组。
常见陷阱
- 忘记众数可能不止一个。
- 值变化时没有把 curCount 重置为 1。
- 只在连续段结束时更新答案，导致漏记（应在每次访问时更新）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private Integer prev = null;
private int curCount = 0;
private int maxCount = 0;
private List<Integer> modes = new ArrayList<>();
public int[] findMode(TreeNode root) {
inorder(root);
int[] ans = new int[modes.size()];
for (int i = 0; i < modes.size(); i++) {
ans[i] = modes.get(i);
}
return ans;
}
private void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
handle(node.val);
inorder(node.right);
}
private void handle(int v) {
if (prev != null && prev == v) {
curCount++;
} else {
curCount = 1;
}
if (curCount > maxCount) {
maxCount = curCount;
modes.clear();
modes.add(v);
} else if (curCount == maxCount) {
modes.add(v);
}
prev = v;
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findMode(root *TreeNode) []int {
var prev *int
curCount, maxCount := 0, 0
modes := []int{}
var handle func(int)
handle = func(v int) {
if prev != nil && *prev == v {
curCount++
} else {
curCount = 1
}
if curCount > maxCount {
maxCount = curCount
modes = []int{v}
} else if curCount == maxCount {
modes = append(modes, v)
}
x := v
prev = &x
}
var inorder func(*TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left)
handle(node.Val)
inorder(node.Right)
}
inorder(root)
return modes
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int curCount = 0;
int maxCount = 0;
TreeNode* prev = nullptr;
vector<int> modes;
vector<int> findMode(TreeNode* root) {
inorder(root);
return modes;
}
void inorder(TreeNode* node) {
if (!node) return;
inorder(node->left);
handle(node);
inorder(node->right);
}
void handle(TreeNode* node) {
if (prev && prev->val == node->val) {
curCount++;
} else {
curCount = 1;
}
if (curCount > maxCount) {
maxCount = curCount;
modes.clear();
modes.push_back(node->val);
} else if (curCount == maxCount) {
modes.push_back(node->val);
}
prev = node;
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
self.prev = None
self.cur_count = 0
self.max_count = 0
self.modes = []
def handle(v: int) -> None:
if self.prev is not None and self.prev == v:
self.cur_count += 1
else:
self.cur_count = 1
if self.cur_count > self.max_count:
self.max_count = self.cur_count
self.modes = [v]
elif self.cur_count == self.max_count:
self.modes.append(v)
self.prev = v
def inorder(node: Optional[TreeNode]) -> None:
if not node:
return
inorder(node.left)
handle(node.val)
inorder(node.right)
inorder(root)
return self.modes/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var findMode = function(root) {
let prev = null;
let curCount = 0;
let maxCount = 0;
const modes = [];
const handle = (v) => {
if (prev !== null && prev === v) {
curCount++;
} else {
curCount = 1;
}
if (curCount > maxCount) {
maxCount = curCount;
modes.length = 0;
modes.push(v);
} else if (curCount === maxCount) {
modes.push(v);
}
prev = v;
};
const inorder = (node) => {
if (!node) return;
inorder(node.left);
handle(node.val);
inorder(node.right);
};
inorder(root);
return modes;
};
Comments