Intermediate Level
Implement the pathSumExistsTree method that checks whether any root-to-leaf path has the target sum.
The input contains a binary tree, its size, and an integer target.
Your task is to check whether the tree has at least one root-to-leaf path whose values add up to target.
A root-to-leaf path starts at the root node and ends at a leaf node. For example, in [5,4,8,11,0,13,4,7,2], one valid path can add up to 22.
Example 1
Input
tree (int[]) =
[5,4,8,11,0,13,4,7,2]size (int) =
9target (int) =
22Returns (boolean)
trueExample 2
Input
tree (int[]) =
[1,2,3]size (int) =
3target (int) =
5Returns (boolean)
falseExample 3
Input
tree (int[]) =
[1,2,3]size (int) =
3target (int) =
3Returns (boolean)
trueUse depth-first search and subtract the current node value from the remaining target.
When visiting a node, reduce the target by that node value. If the node is a leaf, check whether the remaining target becomes 0. If yes, a valid path exists.
Otherwise, continue checking the left and right subtrees. Return true if either side contains a valid path.
Pseudocode:
function pathSumExistsTree(tree, size, target):
return hasPath(0, target)
function hasPath(index, remaining):
if index >= size or tree[index] is missing:
return false
remaining = remaining - tree[index]
left = 2 * index + 1
right = 2 * index + 2
if left has no node and right has no node:
return remaining == 0
return hasPath(left, remaining) or hasPath(right, remaining)Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run