Задача: 563. Binary Tree Tilt
Дано корневое значение бинарного дерева. Вернуть сумму значений наклонов всех узлов дерева.
Наклон узла дерева - это абсолютная разница между суммой всех значений узлов левого поддерева и всех значений узлов правого поддерева. Если у узла нет левого потомка, то сумма значений узлов левого поддерева считается равной 0. То же правило применяется, если у узла нет правого потомка.
Пример:
Input: root = [1,2,3]
Output: 1
Explanation:
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1
👨💻 Алгоритм:
1⃣Определите рекурсивную функцию, которая вычисляет сумму значений узлов поддерева и наклон текущего узла.
2⃣Для каждого узла вычислите сумму значений левого и правого поддерева, а также их наклон, добавляя наклон к общей сумме.
3⃣Верните общую сумму наклонов всех узлов.
😎 Решение:
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
findTilt(root) {
let totalTilt = 0;
function sumAndTilt(node) {
if (node === null) {
return 0;
}
const leftSum = sumAndTilt(node.left);
const rightSum = sumAndTilt(node.right);
const nodeTilt = Math.abs(leftSum - rightSum);
totalTilt += nodeTilt;
return node.val + leftSum + rightSum;
}
sumAndTilt(root);
return totalTilt;
}
}👉Новости 👉Платформа