Проблема
Учитывая root бинарного дерева, уровень его корня равен 1, уровень его дочерних элементов равен 2 и так далее.
Возвратите наименьший уровень x, чтобы сумма всех значений узлов на уровне x была максимальной.
Пример 1:
Input: root = [1,7,0,7,-8,null,null] Output: 2 Explanation: Level 1 sum = 1. Level 2 sum = 7 + 0 = 7. Level 3 sum = 7 + -8 = -1. So we return the level with the maximum sum which is level 2.
Подход
Вы знаете, что сначала мы должны знать сумму этого уровня.
Одна вещь, которую мы можем сделать, это использовать обход по порядку уровней, потому что это будет проходить узлы уровень за уровнем, и мы можем сохранить сумму этого уровня.
Но я хочу сделать это рекурсивным способом, потому что его легко написать, а также оба будут иметь одинаковую временную и пространственную сложность. поэтому я использую обход по порядку, где я отслеживаю уровень в рекурсии и обновляю сумму для этого уровня на карте. после этого я прохожу карту и получаю уровень с максимальной суммой.
Код
Джава
class Solution {
HashMap<Integer, Long> sumMap = new HashMap<>();
public int maxLevelSum(TreeNode root) {
inorder(1, root);
long max = Integer.MIN_VALUE;
int level = 0;
for(int i=1;i<=sumMap.size();i++) {
if(max < sumMap.get(i)) {
max = sumMap.get(i);
level = i;
}
}
return level;
}
public void inorder(int level, TreeNode root) {
if(root == null)
return;
inorder(level+1, root.left);
long levelSumTillNow =
sumMap.getOrDefault(level, 0l) + root.val;
sumMap.put(level, levelSumTillNow);
inorder(level+1, root.right);
}
}
Сложность времени
O(N) для обхода по порядку и O(H) для обхода карты, а поскольку n > h, общая временная сложность будет O(N).
Космическая сложность
O(H) для использования HashMap, где H — высота двоичного дерева.
Вот и все !
