Сложность: medium
Дан корень бинарного дерева, верните длину самого длинного пути последовательных значений.
Путь последовательных значений — это путь, где значения увеличиваются на единицу вдоль пути.
Обратите внимание, что путь может начинаться с любого узла в дереве, и вы не можете перейти от узла к его родителю на пути.
Пример:
Input: root = [1,null,3,2,4,null,null,null,5]
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.
👨💻 Алгоритм:
1⃣Инициализация и начало обхода:
Начните обход дерева с корневого узла. Инициализируйте переменную length, чтобы хранить текущую длину последовательного пути, и передавайте её вниз по дереву.
2⃣Сравнение текущего узла с родительским узлом:
Для каждого узла сравните его значение со значением родительского узла. Если значение текущего узла на единицу больше значения родительского узла, увеличьте length. Если значение текущего узла не является последовательным (не больше на единицу), сбросьте length на 1.
3⃣Обход дерева:
Рекурсивно обходите левое и правое поддерево, передавая обновлённое значение length. В каждом узле обновляйте максимальную длину последовательного пути, если текущая длина больше.
😎 Решение:
class Solution:
def __init__(self):
self.maxLength = 0
def longestConsecutive(self, root: Optional[TreeNode]) -> int:
self.dfs(root, None, 0)
return self.maxLength
def dfs(self, node: Optional[TreeNode], parent: Optional[TreeNode], length: int) -> None:
if not node:
return
if parent and node.val == parent.val + 1:
length += 1
else:
length = 1
self.maxLength = max(self.maxLength, length)
self.dfs(node.left, node, length)
self.dfs(node.right, node, length)
Ставь 👍 и забирай 📚 Базу знаний