501. Find Mode in Binary Search Tree
Дано корень бинарного дерева поиска (BST) с дубликатами. Необходимо вернуть все моды (т.е. самые часто встречающиеся элементы) в этом дереве.
Если в дереве более одной моды, верните их в любом порядке.
Предположим, что BST определяется следующим образом:
Левое поддерево узла содержит только узлы с ключами, меньшими или равными ключу этого узла.
Правое поддерево узла содержит только узлы с ключами, большими или равными ключу этого узла.
Оба поддерева также должны быть бинарными деревьями поиска.
Пример:
Input: root = [1,null,2,2]
Output: [2]
C# решение
сопоставлено/оригиналpublic class Solution {
public int[] FindMode(TreeNode root) {
var values = new List<int>();
Dfs(root, values);
int maxStreak = 0, currStreak = 0, currNum = 0;
var ans = new List<int>();
foreach (int num in values) {
if (num == currNum) {
currStreak++;
} else {
currStreak = 1;
currNum = num;
}
if (currStreak > maxStreak) {
ans.Clear();
ans.Add(num);
maxStreak = currStreak;
} else if (currStreak == maxStreak) {
ans.Add(num);
}
}
return ans.ToArray();
}
private void Dfs(TreeNode node, List<int> values) {
if (node == null) return;
Dfs(node.left, values);
values.Add(node.val);
Dfs(node.right, values);
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public vector<int>& FindMode(TreeNode root) {
var values = new List<int>();
Dfs(root, values);
int maxStreak = 0, currStreak = 0, currNum = 0;
var ans = new List<int>();
foreach (int num in values) {
if (num == currNum) {
currStreak++;
} else {
currStreak = 1;
currNum = num;
}
if (currStreak > maxStreak) {
ans.Clear();
ans.push_back(num);
maxStreak = currStreak;
} else if (currStreak == maxStreak) {
ans.push_back(num);
}
}
return ans.ToArray();
}
private void Dfs(TreeNode node, List<int> values) {
if (node == null) return;
Dfs(node.left, values);
values.push_back(node.val);
Dfs(node.right, values);
}
}Java решение
сопоставлено/оригиналclass Solution {
public int[] findMode(TreeNode root) {
List<Integer> values = new ArrayList();
dfs(root, values);
int maxStreak = 0;
int currStreak = 0;
int currNum = 0;
List<Integer> ans = new ArrayList();
for (int num : values) {
if (num == currNum) {
currStreak++;
} else {
currStreak = 1;
currNum = num;
}
if (currStreak > maxStreak) {
ans = new ArrayList();
maxStreak = currStreak;
}
if (currStreak == maxStreak) {
ans.add(num);
}
}
int[] result = new int[ans.size()];
for (int i = 0; i < ans.size(); i++) {
result[i] = ans.get(i);
}
return result;
}
public void dfs(TreeNode node, List<Integer> values) {
if (node == null) {
return;
}
dfs(node.left, values);
values.add(node.val);
dfs(node.right, values);
}
}JavaScript решение
сопоставлено/оригиналvar findMode = function(root) {
const values = [];
dfs(root, values);
let maxStreak = 0, currStreak = 0, currNum = null;
const ans = [];
for (const num of values) {
if (num === currNum) {
currStreak++;
} else {
currStreak = 1;
currNum = num;
}
if (currStreak > maxStreak) {
ans.length = 0;
ans.push(num);
maxStreak = currStreak;
} else if (currStreak === maxStreak) {
ans.push(num);
}
}
return ans;
};
function dfs(node, values) {
if (!node) return;
dfs(node.left, values);
values.push(node.val);
dfs(node.right, values);
}Python решение
сопоставлено/оригиналclass Solution:
def findMode(self, root: TreeNode) -> List[int]:
values = []
self.dfs(root, values)
max_streak = curr_streak = curr_num = 0
ans = []
for num in values:
if num == curr_num:
curr_streak += 1
else:
curr_streak = 1
curr_num = num
if curr_streak > max_streak:
ans = [num]
max_streak = curr_streak
elif curr_streak == max_streak:
ans.append(num)
return ans
def dfs(self, node, values):
if not node:
return
self.dfs(node.left, values)
values.append(node.val)
self.dfs(node.right, values)Go решение
сопоставлено/оригиналfunc findMode(root *TreeNode) []int {
var values []int
dfs(root, &values)
maxStreak, currStreak, currNum := 0, 0, 0
var ans []int
for _, num := range values {
if num == currNum {
currStreak++
} else {
currStreak = 1
currNum = num
}
if currStreak > maxStreak {
ans = []int{num}
maxStreak = currStreak
} else if currStreak == maxStreak {
ans = append(ans, num)
}
}
return ans
}
func dfs(node *TreeNode, values *[]int) {
if node == nil {
return
}
dfs(node.Left, values)
*values = append(*values, node.Val)
dfs(node.Right, values)
}Algorithm
Обход дерева
Выполните обход дерева (inorder DFS) с использованием рекурсивной функции dfs, чтобы пройти по всем узлам дерева. На каждом узле добавьте node.val в список values.
Поиск мод
Инициализируйте переменные maxStreak, currStreak, currNum как 0 и пустой список ans. Пройдите по списку values. Для каждого числа num: если num равно currNum, увеличьте currStreak. Иначе, установите currStreak равным 1, а currNum равным num. Если currStreak больше maxStreak, обновите maxStreak и сбросьте ans. Если currStreak равен maxStreak, добавьте num в ans.
Возврат результата
Верните список ans.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.