Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
Objective: Find if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
Constraints:
1. The number of nodes in the tree is in the range [0, 5000].
2. -1000 <= Node.val <= 1000
3. -1000 <= targetSum <= 1000
Edge Cases:
1. Empty Tree
2. Tree Nodes w/ only positive values
3. Tree Nodes w/ only negative values
4. Tree Nodes w/ mixed positive and negative values
*I tried to reduce time by not adding to child once the sum of values has exceeded target value. However, if there is a mixed positive and negative values, you cannot use this criteria to judge whether you should try out that path.
How it works:
1. Check if the current node is a leaf and if target value is reached. If so, short circuit and return True
2. Add node.left and node.right to the stack of nodes_to_visit. (The values in their node tuple will be the sum of values to reach that node + the value of node)
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
node_tuple = None
# When the Tree is empty
if root:
node_tuple = (root, root.val)
nodes_to_visit = []
while node_tuple:
node, val = node_tuple
is_leaf = not node.left and not node.right
# If the node is leaf and the pathsum equals the target sum
if is_leaf and val == targetSum:
return True
# Adding left and right child node to nodes_to_visit stack
if node.left:
nodes_to_visit.append((node.left, val + node.left.val))
if node.right:
nodes_to_visit.append((node.right, val + node.right.val))
# Checking if we've traversed through the whole tree
if nodes_to_visit:
node_tuple = nodes_to_visit.pop()
else:
node_tuple = None
return False
LeetCode Question #112