Вот проблема
Существует бинарное дерево с корнем 0, состоящее из n узлов. Узлы помечены от 0 до n - 1. Вам дан 0-индексированный целочисленный массив parents, представляющий дерево, где parents[i] является родителем узла i. Поскольку узел 0 является корнем, parents[0] == -1.
У каждого узла есть оценка. Чтобы найти оценку узла, проверьте, были ли узел и связанные с ним ребра удалены. Дерево станет одним или несколькими непустыми поддеревьями. Размер поддерева — это количество узлов в нем. Оценка узла — это произведение размеров всех этих поддеревьев.
Возвращает количество узлов с наибольшей оценкой.
Пример 1:
Input: parents = [-1,2,0,2,0] Output: 3 Explanation: - The score of node 0 is: 3 * 1 = 3 - The score of node 1 is: 4 = 4 - The score of node 2 is: 1 * 1 * 2 = 2 - The score of node 3 is: 4 = 4 - The score of node 4 is: 4 = 4 The highest score is 4, and three nodes (node 1, node 3, and node 4) have the highest score.
Пример 2:
Input: parents = [-1,2,0] Output: 2 Explanation: - The score of node 0 is: 2 = 2 - The score of node 1 is: 2 = 2 - The score of node 2 is: 1 * 1 = 1 The highest score is 2, and two nodes (node 0 and node 1) have the highest score.
Вот решение
function countHighestScoreNodes(parents) {
const totalNodes = parents.length;
const children = createChildrenMap(parents);
let maxProd = 0;
let maxProdCount = 0;
const memo = new Array(parents.length).fill(undefined);
dfs(parents[0]);
return maxProdCount;
function dfs(node) {
if (node == undefined) return 0;
if (memo[node] !== undefined) return memo[node];
const [one, two] = children.get(node) ?? [];
const childOneSize = dfs(one);
const childTwoSize = dfs(two);
const restSize = totalNodes - childOneSize - childTwoSize - 1;
const prod = [childOneSize, childTwoSize, restSize]
.filter(Boolean)
.reduce((val, prod) => val * prod, 1);
if (maxProd < prod) {
maxProd = prod;
maxProdCount = 1;
} else if (maxProd === prod) {
maxProdCount++;
}
memo[node] = childOneSize + childTwoSize + 1;
return memo[node];
}
function createChildrenMap(parents) {
const children = new Map();
for (let i = 0; i < parents.length; i++) {
const parent = parents[i];
children.set(parent, (children.get(parent) ?? []).concat(i));
}
return children;
}
}
Эта строка объявляет основную функцию и присваивает общее количество узлов в дереве переменной totalNodes.
function countHighestScoreNodes(parents) {
const totalNodes = parents.length;
Эта строка вызывает функцию createChildrenMap, передавая массив parents в качестве аргумента, и присваивает возвращаемое значение переменной children. Эта функция создает карту, где ключами являются родительские узлы, а значениями являются массивы их дочерних узлов.
const children = createChildrenMap(parents);
Эти строки объявляют переменные maxProd и maxProdCount и инициализируют их значением 0. maxProd хранит максимальное произведение размеров трех групп узлов (дочерние, внуки и остальная часть дерева), а maxProdCount подсчитывает количество раз, которое maxProd имеет место.
let maxProd = 0; let maxProdCount = 0;
Эта строка объявляет массив memo с parents.length элементами и заполняет его undefined . Этот массив будет использоваться для хранения результатов ранее вычисленных вызовов dfs для целей запоминания.
const memo = new Array(parents.length).fill(undefined);
Эта строка вызывает функцию dfs, передавая в качестве аргумента корневой узел дерева. Эта функция является рекурсивной функцией, которая проходит по дереву в порядке глубины и вычисляет размер дочерних элементов, внуков и остальной части дерева для каждого узла.
dfs(parents[0]);
Эта строка возвращает окончательное значение maxProdCount, которое представляет собой количество раз, когда встречается максимальное произведение размеров трех групп узлов.
return maxProdCount;
Эта строка является началом функции dfs. Функция принимает один параметр, текущий посещаемый узел. Если текущий узел не определен, функция возвращает 0.
function dfs(node) {
if (node == undefined) return 0;
Эта строка проверяет, был ли уже вычислен результат текущего узла и сохранен ли он в массиве мемоизации. Если это так, функция возвращает сохраненный результат.
if (memo[node] !== undefined) return memo[node];
Эта строка удаляет дочерние элементы текущего узла из карты children. Если для текущего узла нет дочерних элементов, назначение деструктурирования назначает пустой массив one и two.
const [one, two] = children.get(node) ?? [];
Эти строки рекурсивно вызывают функцию dfs, передавая в качестве аргументов первого и второго дочерних элементов текущего узла. Функция вызывается дважды, по одному разу для каждого потомка, а возвращаемые значения присваиваются childOneSize и childTwoSize соответственно. Эти значения представляют размер потомков и внуков текущего узла.
const childOneSize = dfs(one);
const childTwoSize = dfs(two);
Эта строка вычисляет размер остальной части дерева, которая не является потомком или внуком текущего узла. Он вычитает размеры потомков и внуков из общего количества узлов и вычитает 1, чтобы исключить текущий узел из расчета.
const restSize = totalNodes - childOneSize - childTwoSize - 1;
Эта строка вычисляет произведение размеров трех групп узлов (детей, внуков и остальной части дерева). Он создает массив [childOneSize, childTwoSize, restSize] , отфильтровывает любые ложные значения, а затем использует метод сокращения для умножения всех элементов массива вместе. Результат сохраняется в переменной prod.
const prod = [childOneSize, childTwoSize, restSize]
.filter(Boolean)
.reduce((val, prod) => val * prod, 1);
Этот блок кода сравнивает текущий продукт prod с текущим максимальным продуктом maxProd. Если prod больше maxProd, maxProd обновляется до prod, а maxProdCount сбрасывается до 1. Если prod равно maxProd, maxProdCount увеличивается на 1.
if (maxProd < prod) {
maxProd = prod;
maxProdCount = 1;
} else if (maxProd === prod) {
maxProdCount++;
}
Эта строка сохраняет результат текущего узла в массиве мемоизации, а затем функция возвращает размер поддерева текущего узла.
memo[node] = childOneSize + childTwoSize + 1;
return memo[node];
Это функция createChildrenMap, которая принимает в качестве аргумента массив parents. Он создает новую карту, children, и перебирает массив parents. Для каждого элемента в массиве он добавляет текущий индекс в качестве дочернего к соответствующему родительскому узлу на карте. Если у родительского узла еще нет дочерних элементов, он добавляет пустой массив в качестве значения. Наконец, он возвращает карту children.
function createChildrenMap(parents) {
const children = new Map();
for (let i = 0; i < parents.length; i++) {
const parent = parents[i];
children.set(parent, (children.get(parent) ?? []).concat(i));
}
return children;
}
Таким образом, в целом эта реализация более эффективна за счет использования мемоизации, она позволяет избежать многократного пересчета размера дочерних элементов для одного и того же узла, что значительно снижает временную сложность решения до O (n), где n — количество узлов в дереве. .
