Сложность: medium
Дан корень двоичного дерева, верните самое левое значение в последней строке дерева.
Пример:
Input: root = [2,1,3]
Output: 1
👨💻 Алгоритм:
1⃣Инициализируйте переменную maxDepth для хранения глубины нижнего уровня дерева. Инициализируйте переменную bottomLeftValue для хранения самого левого значения в последней строке дерева.
2⃣Реализуйте рекурсивную функцию dfs, которая обходит дерево и находит самое левое значение в последней строке дерева. Параметры функции: current (текущий узел) и depth (его глубина). Проверьте, пуст ли текущий узел. Если да, то вернитесь.
3⃣Проверьте, превышает ли текущая глубина глобальную переменную maxDepth. Если да, это значит, что мы нашли новый уровень. Установите maxDepth в значение текущей глубины. Установите bottomLeftValue в значение текущего узла. Рекурсивно вызовите dfs для левого поддерева текущего узла, увеличив глубину на один. Рекурсивно вызовите dfs для правого поддерева текущего узла, увеличив глубину на один. Вызовите dfs с корнем и начальной глубиной 0. Верните bottomLeftValue.
😎 Решение:
class Solution {
var maxDepth = -1
var bottomLeftValue = 0
func findBottomLeftValue(_ root: TreeNode?) -> Int {
dfs(root, 0)
return bottomLeftValue
}
func dfs(_ current: TreeNode?, _ depth: Int) {
guard let current = current else { return }
if depth > maxDepth {
maxDepth = depth
bottomLeftValue = current.val
}
dfs(current.left, depth + 1)
dfs(current.right, depth + 1)
}
}Ставь 👍 и забирай 📚 Базу знаний