# Question

Formatted question description: https://leetcode.ca/all/112.html

112	Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path
such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,
5
/ \
4   8
/   / \
11  13  4
/  \      \
7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

@tag-tree


# Algorithm

Use recursion to constantly find the left and right child nodes of the child node, and the parameters of calling the recursive function are only the current node and the sum value.

First of all, if the input is an empty node, it will directly return false. If the input is only one root node, compare the value of the current root node and the parameter sum if the value is the same. If they are the same, return true, otherwise false. This condition is also the termination condition of recursion.

The next step is to start recursion. Since the return value of the function is True/False, you can recurse in both directions at the same time, using or || in the middle to connect. As long as one of them is True, the whole result is True. When recursing left and right nodes, the sum value at this time should be the original sum value minus the value of the current node.

Java