Сложность: medium
Если глубина дерева меньше 5, то это дерево можно представить в виде массива трехзначных чисел. Для каждого числа в этом массиве:
Сотни представляют глубину d этого узла, где 1 <= d <= 4.
Десятки представляют позицию p этого узла на уровне, которому он принадлежит, где 1 <= p <= 8. Позиция соответствует позиции в полном бинарном дереве.
Единицы представляют значение v этого узла, где 0 <= v <= 9.
Дан массив возрастающих трехзначных чисел nums, представляющих бинарное дерево с глубиной меньше 5. Верните сумму всех путей от корня к листьям.
Гарантируется, что данный массив представляет собой валидное связанное бинарное дерево.
Пример:
Input: nums = [113,215,221]
Output: 12
Explanation: The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.
👨💻 Алгоритм:
1⃣Создание структуры дерева:
Пройдите по массиву nums и для каждого элемента создайте узел дерева.
Сохраните узлы в словаре для удобного доступа по их позиции.
2⃣Связывание узлов:
Пройдите по массиву и свяжите узлы друг с другом, исходя из их позиции и глубины.
Найдите левого и правого ребенка для каждого узла и установите соответствующие связи.
3⃣Подсчет суммы путей:
Выполните обход дерева (например, используя DFS) и подсчитайте сумму всех путей от корня к листьям.
😎 Решение:
var pathSum = function(nums) {
let tree = new Map();
for (let num of nums) {
let depth = Math.floor(num / 100);
let pos = Math.floor(num / 10) % 10;
let val = num % 10;
tree.set(depth * 10 + pos, val);
}
return dfs(tree, 1, 1, 0);
};
function dfs(tree, depth, pos, currentSum) {
let key = depth * 10 + pos;
if (!tree.has(key)) {
return 0;
}
currentSum += tree.get(key);
let leftChild = (depth + 1) * 10 + 2 * pos - 1;
let rightChild = (depth + 1) * 10 + 2 * pos;
if (!tree.has(leftChild) && !tree.has(rightChild)) {
return currentSum;
}
return dfs(tree, depth + 1, 2 * pos - 1, currentSum) + dfs(tree, depth + 1, 2 * pos, currentSum);
}Ставь 👍 и забирай 📚 Базу знаний