Сложность: Medium
Дан корень бинарного дерева и целое число targetSum. Верните все пути от корня до листа, где сумма значений узлов в пути равна targetSum. Каждый путь должен быть возвращён как список значений узлов, а не ссылок на узлы.
Путь от корня до листа — это путь, начинающийся от корня и заканчивающийся на любом листовом узле. Лист — это узел без детей.
Пример:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
👨💻 Алгоритм:
1️⃣Определение функции recurseTree: Функция принимает текущий узел (node), оставшуюся сумму (remainingSum), которая необходима для продолжения поиска вниз по дереву, и список узлов (pathNodes), который содержит все узлы, встреченные до текущего момента на данной ветке.
2️⃣Проверка условий: На каждом шаге проверяется, равна ли оставшаяся сумма значению текущего узла. Если это так и текущий узел является листом, текущий путь (pathNodes) добавляется в итоговый список путей, который должен быть возвращен.
3️⃣Обработка всех ветвей: Учитывая, что значения узлов могут быть отрицательными, необходимо исследовать все ветви дерева до самых листьев, независимо от текущей суммы по пути.
😎 Решение:
class TreeNode:
def __init__(self, x: int) -> None:
self.val = x
self.left = None
self.right = None
class Solution:
def recurseTree(
self,
node: TreeNode,
remainingSum: int,
pathNodes: List[int],
pathsList: List[List[int]],
) -> None:
if not node:
return
pathNodes.append(node.val)
if remainingSum == node.val and not node.left and not node.right:
pathsList.append(list(pathNodes))
else:
self.recurseTree(
node.left, remainingSum - node.val, pathNodes, pathsList
)
self.recurseTree(
node.right, remainingSum - node.val, pathNodes, pathsList
)
pathNodes.pop()
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
pathsList = []
self.recurseTree(root, sum, [], pathsList)
return pathsList
Ставь 👍 и забирай 📚 Базу знаний