Tree - Path Sum
All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.
Difficulty : Easy
DFS
Problem
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.
Example 1:
1
2
3
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.
Example 2:
1
2
3
4
5
6
Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.
Solution
Since the sum is different for each path we need to track it for every traversal. A simple way to implement this is add it as a function argument. The function call stack will preserve all the intermediate values as calculated at each node level.
Our dfs() function will look like this:
1
2
def dfs(root, path_sum):
...
As always, we shall start with the base case. Whenever we reach a leaf node we can compare if the path_sum==target_sum and return the boolean result.
1
2
if not root.left and not root.right:
return path_sum==target_sum
However, before we compare path_sum==target_sum, we need to update path_sum.
1
path_sum +=root.val
The next step is to traverse through the tree.
1
2
3
4
5
6
if root.left and root.right:
return dfs(root.left,path_sum) or dfs(root.right,path_sum)
elif root.left:
return dfs(root.left,path_sum)
else:
return dfs(root.right,path_sum)
In case of a edge case where root=[], you can validate that before calling the dfs() function.
1
2
if not root:
return False
Finally return the dfs(root,0).
1
return dfs(root,0)
Final Code
Here is the full code.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def has_path_sum(root, target_sum):
if not root:
return False
def dfs(root,path_sum):
path_sum+= root.val
if not root.left and not root.right:
return path_sum == target_sum
if root.left and root.right:
return dfs(root.left,path_sum) or dfs(root.right,path_sum)
elif root.left:
return dfs(root.left,path_sum)
else:
return dfs(root.right,path_sum)
return dfs(root,0)
Now, there is a bit shorter version. Here is the code below. If you have understood the above code, the below one should be very similar to understand.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def has_path_sum(root, target_sum):
def dfs(root,path_sum):
if not root:
return False
path_sum+= root.val
if not root.left and not root.right:
return path_sum == target_sum
return dfs(root.left,path_sum) or dfs(root.right,path_sum)
return dfs(root,0)