113. Path Sum II

public class Solution {
    private void RecurseTree(TreeNode node, int remainingSum,
                             List<int> pathNodes, IList<IList<int>> pathsList) {
        if (node == null) {
            return;
        }
        pathNodes.Add(node.val);
        if (remainingSum == node.val && node.left == null && node.right == null) {
            pathsList.Add(new List<int>(pathNodes));
        } else {
            this.RecurseTree(node.left, remainingSum - node.val, pathNodes, pathsList);
            this.RecurseTree(node.right, remainingSum - node.val, pathNodes, pathsList);
        }
        pathNodes.RemoveAt(pathNodes.Count - 1);
    }
    public IList<IList<int>> PathSum(TreeNode root, int sum) {
        List<IList<int>> pathsList = new List<IList<int>>();
        List<int> pathNodes = new List<int>();
        this.RecurseTree(root, sum, pathNodes, pathsList);
        return pathsList;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private void RecurseTree(TreeNode node, int remainingSum,
                             List<int> pathNodes, IList<vector<int>> pathsList) {
        if (node == null) {
            return;
        }
        pathNodes.push_back(node.val);
        if (remainingSum == node.val && node.left == null && node.right == null) {
            pathsList.push_back(new List<int>(pathNodes));
        } else {
            this.RecurseTree(node.left, remainingSum - node.val, pathNodes, pathsList);
            this.RecurseTree(node.right, remainingSum - node.val, pathNodes, pathsList);
        }
        pathNodes.RemoveAt(pathNodes.size() - 1);
    }
    public IList<vector<int>> PathSum(TreeNode root, int sum) {
        List<vector<int>> pathsList = new List<vector<int>>();
        List<int> pathNodes = new List<int>();
        this.RecurseTree(root, sum, pathNodes, pathsList);
        return pathsList;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private void recurseTree(
        TreeNode node,
        int remainingSum,
        List<Integer> pathNodes,
        List<List<Integer>> pathsList
    ) {
        if (node == null) {
            return;
        }

        pathNodes.add(node.val);

        if (remainingSum == node.val && node.left == null && node.right == null) {
            pathsList.add(new ArrayList<>(pathNodes));
        } else {
            this.recurseTree(
                    node.left,
                    remainingSum - node.val,
                    pathNodes,
                    pathsList
                );
            this.recurseTree(
                    node.right,
                    remainingSum - node.val,
                    pathNodes,
                    pathsList
                );
        }

        pathNodes.remove(pathNodes.size() - 1);
    }

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> pathsList = new ArrayList<>();
        List<Integer> pathNodes = new ArrayList<>();
        this.recurseTree(root, sum, pathNodes, pathsList);
        return pathsList;
    }
}

var pathSum = function (root, sum) {
    let pathsList = [];
    let pathNodes = [];
    let recurseTree = function (node, remainingSum, pathNodes, pathsList) {
        if (!node) {
            return;
        }
        pathNodes.push(node.val);
        if (
            remainingSum === node.val &&
            node.left === null &&
            node.right === null
        ) {
            pathsList.push(Array.from(pathNodes));
        } else {
            recurseTree(
                node.left,
                remainingSum - node.val,
                pathNodes,
                pathsList,
            );
            recurseTree(
                node.right,
                remainingSum - node.val,
                pathNodes,
                pathsList,
            );
        }
        pathNodes.pop();
    };
    recurseTree(root, sum, pathNodes, pathsList);
    return pathsList;
};

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

func pathSum(root *TreeNode, sum int) [][]int {
    pathsList := [][]int{}
    pathNodes := []int{}
    var recurseTree func(*TreeNode, int, []int, [][]int) [][]int
    recurseTree = func(node *TreeNode, remainingSum int, pathNodes []int, pathsList [][]int) [][]int {
        if node == nil {
            return pathsList
        }
        pathNodes = append(pathNodes, node.Val)
        if remainingSum == node.Val && node.Left == nil && node.Right == nil {
            tmp := make([]int, len(pathNodes))
            copy(tmp, pathNodes)
            pathsList = append(pathsList, tmp)
        } else {
            pathsList = recurseTree(node.Left, remainingSum-node.Val, pathNodes, pathsList)
            pathsList = recurseTree(node.Right, remainingSum-node.Val, pathNodes, pathsList)
        }
        pathNodes = pathNodes[:len(pathNodes)-1]
        return pathsList
    }
    return recurseTree(root, sum, pathNodes, pathsList)
}

Algorithm

1️⃣

Определение функции recurseTree: Функция принимает текущий узел (node), оставшуюся сумму (remainingSum), которая необходима для продолжения поиска вниз по дереву, и список узлов (pathNodes), который содержит все узлы, встреченные до текущего момента на данной ветке.

2️⃣

Проверка условий: На каждом шаге проверяется, равна ли оставшаяся сумма значению текущего узла. Если это так и текущий узел является листом, текущий путь (pathNodes) добавляется в итоговый список путей, который должен быть возвращен.

3️⃣

Обработка всех ветвей: Учитывая, что значения узлов могут быть отрицательными, необходимо исследовать все ветви дерева до самых листьев, независимо от текущей суммы по пути.

😎