700454. Root to leaf paths sum
Here is the detailed Markdown blog post for the problem "Root to leaf paths sum":
Root to Leaf Paths Sum
Summary
Given a binary tree, find all the root-to-leaf paths where the sum of node values is equal to a given target sum. The problem requires traversing the tree and calculating the sum of node values along each path from the root to a leaf.
Detailed Explanation
To solve this problem, we can use a recursive approach. We start by visiting the root node and recursively traverse the left and right subtrees. For each subtree, we calculate the sum of node values and compare it with the target sum. If the sum is equal to the target sum, we have found a root-to-leaf path that meets the condition.
Here's a step-by-step breakdown of the solution:
- Define a recursive function
sumPathsthat takes three parameters: the current node, the target sum, and a boolean flag indicating whether we are currently on a leaf path. - Initialize the sum of the current path to 0.
- If the current node is a leaf node (i.e., it has no children), check if the sum of the current path is equal to the target sum. If it is, return the path.
- Recursively call
sumPathson the left and right subtrees with the updated sum and the same leaf flag. - Update the sum of the current path by adding the value of the current node.
Here's an ASCII art diagram illustrating the recursive traversal:
1
/ \
2 3
/ \ /
4 5 6
Time complexity: O(N), where N is the number of nodes in the tree. This is because we visit each node once.
Space complexity: O(H), where H is the height of the tree. This is because of the recursive call stack.
Optimized Solutions
Java
class Solution {
public List<String> pathSum(TreeNode root, int sum) {
List<String> result = new ArrayList<>();
sumPaths(root, sum, "", result);
return result;
}
private void sumPaths(TreeNode node, int sum, String path, List<String> result) {
if (node == null) return;
sum += node.val;
path += node.val + "->";
if (node.left == null && node.right == null) {
if (sum == 0) result.add(path.substring(0, path.length() - 2));
} else {
sumPaths(node.left, sum, path, result);
sumPaths(node.right, sum, path, result);
}
}
}