Sponsored
Sponsored
This approach uses an inorder traversal to exploit the nature of BSTs, where an inorder traversal yields elements in sorted order. Utilize a HashMap (or equivalent) to count the frequency of each element. Traverse the tree, update frequencies, and then determine the mode(s) based on maximum frequency.
Time Complexity: O(n), as each node is visited twice. Space Complexity: O(n) due to the recursion stack and the use of an array to store the modes.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] FindMode(TreeNode root) {
6 var freq = new Dictionary<int, int>();
7 Inorder(root, freq);
8 int maxFreq = GetMaxFreq(freq);
9 var modes = new List<int>();
10 foreach (var kvp in freq) {
11 if (kvp.Value == maxFreq) {
12 modes.Add(kvp.Key);
13 }
14 }
15 return modes.ToArray();
16 }
17
18 private void Inorder(TreeNode root, Dictionary<int, int> freq) {
19 if (root == null) return;
20 Inorder(root.left, freq);
21 if (freq.ContainsKey(root.val)) {
22 freq[root.val]++;
23 } else {
24 freq[root.val] = 1;
25 }
26 Inorder(root.right, freq);
27 }
28
29 private int GetMaxFreq(Dictionary<int, int> freq) {
30 int maxFreq = 0;
31 foreach (var count in freq.Values) {
32 if (count > maxFreq) {
33 maxFreq = count;
34 }
35 }
36 return maxFreq;
37 }
38}The C# solution operates similar to others, employing a dictionary for the frequency count and looping to find modes.
Morris Traversal allows inorder traversal without using additional stack space, which could be advantageous in follow-up scenarios described by the problem constraints. By threading the tree, we can traverse without recursion or explicit stack, maintaining a space complexity of O(1).
Time Complexity: O(n), Space Complexity: O(1).
1using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> findMode(TreeNode* root) {
// Placeholder for Morris Traversal approach.
return vector<int>();
}
};This C++ version outlines Morris Traversal’s merit in the context but doesn’t implement the full mode calculation, due to space complexity advantages and problem nuances.