Description:
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.
Examples:
Example 1:
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:
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.
Example 3:
Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.Solution in Python:
To solve the problem of determining if a binary tree has a root-to-leaf path that sums up to a given target sum, we will use a Depth-First Search (DFS) approach. This method involves recursively traversing the tree, keeping track of the current path sum, and checking if we have reached a leaf node that meets the target sum.
Python
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
# Helper function to perform DFS on the tree
def dfs(node, current_sum):
# If the node is None, return False (base case)
if not node:
return False
# Update the current sum by adding the node's value
current_sum += node.val
# Check if the current node is a leaf and if its path sum equals the targetSum
if not node.left and not node.right:
return current_sum == targetSum
# Recursively check the left and right subtrees
left_has_sum = dfs(node.left, current_sum)
right_has_sum = dfs(node.right, current_sum)
# Return True if either subtree has a path sum equal to the targetSum
return left_has_sum or right_has_sum
# Start the DFS from the root with an initial sum of 0
return dfs(root, 0)Detailed Comments:
- TreeNode Class Definition:
- The
TreeNodeclass represents the structure of a node in a binary tree. Each node contains an integer value (val), and pointers to its left and right children (leftandright).
- The
- hasPathSum Function:
- Input Parameters: The function takes two parameters:
root, which is the root of the binary tree, andtargetSum, which is the target sum we are looking for. - Helper Function (dfs):
- The helper function
dfsperforms a Depth-First Search on the tree. - Base Case: If the current node is
None, it means we have reached the end of a path without finding the target sum, so we returnFalse. - Current Sum Update: We update the
current_sumby adding the value of the current node. - Leaf Node Check: If the current node is a leaf (i.e., it has no left or right children), we check if the
current_sumequals thetargetSum. If it does, we returnTrue. - Recursive Calls: We recursively call the
dfsfunction on the left and right children of the current node, passing the updatedcurrent_sum. - Return Condition: The function returns
Trueif either the left or the right subtree has a path that sums to thetargetSum.
- The helper function
- DFS Initialization: We initiate the DFS from the
rootwith an initialcurrent_sumof0.
- Input Parameters: The function takes two parameters:
This approach ensures that we explore all possible root-to-leaf paths in the binary tree, checking if any path meets the target sum. The time complexity is O(n), where nnn is the number of nodes in the tree, as each node is processed once. The space complexity is O(h), where hhh is the height of the tree, representing the maximum depth of the recursion stack.
Solution in Javascript:
JavaScript
/**
* @param {TreeNode} root
* @param {number} targetSum
* @return {boolean}
*/
var hasPathSum = function(root, targetSum) {
// Helper function to perform DFS on the tree
const dfs = (node, currentSum) => {
// If the node is null, return false (base case)
if (node === null) {
return false;
}
// Update the current sum by adding the node's value
currentSum += node.val;
// Check if the current node is a leaf and if its path sum equals the targetSum
if (node.left === null && node.right === null) {
return currentSum === targetSum;
}
// Recursively check the left and right subtrees
const leftHasSum = dfs(node.left, currentSum);
const rightHasSum = dfs(node.right, currentSum);
// Return true if either subtree has a path sum equal to the targetSum
return leftHasSum || rightHasSum;
};
// Start the DFS from the root with an initial sum of 0
return dfs(root, 0);
};Solution in Java:
Java
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
// Start the DFS from the root with the initial sum of 0
return dfs(root, targetSum);
}
// Helper function to perform DFS on the tree
private boolean dfs(TreeNode node, int targetSum) {
// If the node is null, return false (base case)
if (node == null) {
return false;
}
// Update the target sum by subtracting the node's value
targetSum -= node.val;
// Check if the current node is a leaf
if (node.left == null && node.right == null) {
// If the remaining target sum is 0, return true
return targetSum == 0;
}
// Recursively check the left and right subtrees
boolean leftHasSum = dfs(node.left, targetSum);
boolean rightHasSum = dfs(node.right, targetSum);
// Return true if either subtree has a path sum equal to the target sum
return leftHasSum || rightHasSum;
}
}Solution in C#:
C#
public class Solution {
public bool HasPathSum(TreeNode root, int targetSum) {
// Start the DFS from the root
return Dfs(root, targetSum);
}
// Helper function to perform DFS on the tree
private bool Dfs(TreeNode node, int targetSum) {
// If the node is null, return false (base case)
if (node == null) {
return false;
}
// Update the target sum by subtracting the node's value
targetSum -= node.val;
// Check if the current node is a leaf
if (node.left == null && node.right == null) {
// If the remaining target sum is 0, return true
return targetSum == 0;
}
// Recursively check the left and right subtrees
bool leftHasSum = Dfs(node.left, targetSum);
bool rightHasSum = Dfs(node.right, targetSum);
// Return true if either subtree has a path sum equal to the target sum
return leftHasSum || rightHasSum;
}
}