given the root of a binary tree and an integer target find the number of paths where the sum of the values along the path equals target leetcode reference https leetcode comproblemspathsumiii a node has value variable and pointers to nodes to its left and right target int def initself none self paths 0 def depthfirstsearchself node node none pathsum int none if node is none return if pathsum self target self paths 1 if node left self depthfirstsearchnode left pathsum node left value if node right self depthfirstsearchnode right pathsum node right value def pathsumself node node none target int none none int if node is none return 0 if target is not none self target target self depthfirstsearchnode node value self pathsumnode left self pathsumnode right return self paths if name main import doctest doctest testmod a node has value variable and pointers to nodes to its left and right the below tree looks like this 10 5 3 3 2 11 3 2 1 tree node 10 tree left node 5 tree right node 3 tree left left node 3 tree left right node 2 tree right right node 11 tree left left left node 3 tree left left right node 2 tree left right right node 1 binarytreepathsum path_sum tree 8 3 binarytreepathsum path_sum tree 7 2 tree right right node 10 binarytreepathsum path_sum tree 8 2
from __future__ import annotations


class Node:
    

    def __init__(self, value: int) -> None:
        self.value = value
        self.left: Node | None = None
        self.right: Node | None = None


class BinaryTreePathSum:
    r

    target: int

    def __init__(self) -> None:
        self.paths = 0

    def depth_first_search(self, node: Node | None, path_sum: int) -> None:
        if node is None:
            return

        if path_sum == self.target:
            self.paths += 1

        if node.left:
            self.depth_first_search(node.left, path_sum + node.left.value)
        if node.right:
            self.depth_first_search(node.right, path_sum + node.right.value)

    def path_sum(self, node: Node | None, target: int | None = None) -> int:
        if node is None:
            return 0
        if target is not None:
            self.target = target

        self.depth_first_search(node, node.value)
        self.path_sum(node.left)
        self.path_sum(node.right)

        return self.paths


if __name__ == "__main__":
    import doctest

    doctest.testmod()