Сложность: medium
Дано корень бинарного дерева, верните длину самого длинного пути, на котором все узлы имеют одинаковое значение. Этот путь может проходить через корень или не проходить.
Длина пути между двумя узлами представлена количеством рёбер между ними.
Пример:
Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 5).
👨💻 Алгоритм:
1⃣Определить рекурсивную функцию solve(), принимающую текущий узел root и значение родительского узла parent. Если root равен NULL, вернуть 0. Рекурсивно вызвать solve() для левого и правого дочернего узлов, передав значение текущего узла как значение родительского узла.
2⃣Обновить переменную ans, если сумма значений для левого и правого узлов больше текущего значения ans. Если значение текущего узла равно значению родительского узла, вернуть max(left, right) + 1, иначе вернуть 0.
3⃣Вызвать solve() с корневым узлом и значением родительского узла -1. Вернуть максимальную длину пути ans..
😎 Решение:
class Solution {
var ans = 0
func solve(_ root: TreeNode?, _ parent: Int) -> Int {
guard let root = root else { return 0 }
let left = solve(root.left, root.val)
let right = solve(root.right, root.val)
ans = max(ans, left + right)
return root.val == parent ? max(left, right) + 1 : 0
}
func longestUnivaluePath(_ root: TreeNode?) -> Int {
solve(root, -1)
return ans
}
}Ставь 👍 и забирай 📚 Базу знаний