Задача: 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⃣Верните общую сумму наклонов всех узлов.
😎 Решение:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
private int totalTilt = 0;
public int findTilt(TreeNode root) {
sumAndTilt(root);
return totalTilt;
}
private int sumAndTilt(TreeNode node) {
if (node == null) {
return 0;
}
int leftSum = sumAndTilt(node.left);
int rightSum = sumAndTilt(node.right);
int nodeTilt = Math.abs(leftSum - rightSum);
totalTilt += nodeTilt;
return node.val + leftSum + rightSum;
}
}👉Новости 👉База вопросов