grid47 Exploring patterns and algorithms
Oct 26, 2024
6 min read
Solution to LeetCode 113: Path Sum II Problem
Given the root of a binary tree and an integer targetSum, return all paths from the root to the leaf nodes where the sum of the node values along the path equals the targetSum. A root-to-leaf path is defined as any path that starts from the root and ends at a leaf node. A leaf node is a node that does not have any children.
Problem
Approach
Steps
Complexity
Input: The input consists of a binary tree represented by the root node and an integer targetSum. The binary tree is represented as an array where each node is given by its value. Null values represent missing nodes.
• The number of nodes in the tree is in the range [0, 5000].
• Each node value is between -1000 and 1000.
• The targetSum is between -1000 and 1000.
Output: The output should be a list of all root-to-leaf paths, where each path is represented as a list of node values that sum up to the given targetSum.
Example: Output: [[10,5,3], [10,15,20]]
Constraints:
• Each path should be a valid root-to-leaf path with the sum of node values equal to targetSum.
Goal: The goal is to traverse the tree and accumulate the path sum from the root to the leaf nodes. If a path's sum matches the targetSum, it should be added to the result.
Steps:
• Traverse the tree using depth-first search (DFS).
• At each node, subtract its value from targetSum and continue exploring both left and right children.
• If a leaf node is reached and the remaining sum equals 0, add the current path to the result.
Goal: The tree may have up to 5000 nodes, and each node's value can range from -1000 to 1000. The solution should handle these efficiently.
Steps:
• Tree size: 0 <= number of nodes <= 5000
• Node values: -1000 <= Node.val <= 1000
• Target sum: -1000 <= targetSum <= 1000
Assumptions:
• The input tree is a valid binary tree, where nodes have either zero, one, or two children.
• Explanation: Starting from the root (10), we explore the left child (5) and its left child (3), which gives the path [10,5,3] with sum 22. We also explore the right child (15) and its right child (20), which gives the path [10,15,20] with sum 22.
• Input: Input: root = [1,2,3], targetSum = 5
• Explanation: No path from root to leaf sums up to 5. Therefore, the output is an empty list.
Approach: The solution involves using depth-first search (DFS) to traverse the tree. At each node, we reduce the targetSum by the current node value. If we reach a leaf node with the remaining targetSum equal to 0, we add that path to the result.
Observations:
• DFS is ideal for exploring all possible root-to-leaf paths.
• We need to ensure that when we reach a leaf node, we check if the path sum equals the targetSum.
Steps:
• Perform a DFS traversal starting from the root node.
• At each node, subtract the node value from the targetSum and store the current path.
• When a leaf node is reached, if the targetSum is 0, add the path to the result.
• Backtrack by removing the last node from the path after exploring both left and right subtrees.
Empty Inputs:
• If the tree is empty (root is null), the output should be an empty list.
Large Inputs:
• The solution should efficiently handle trees with up to 5000 nodes.
Special Values:
• Handle negative targetSum and node values, ensuring the path sum calculation is correct even when values are negative.
Constraints:
• The solution should operate within time and space limits for trees with up to 5000 nodes.
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> paths;
vector<int> path;
findPaths(root, sum, path, paths);
return paths;
}
voidfindPaths(TreeNode* node, int sum, vector<int>& path, vector<vector<int>>& paths) {
if (!node) return;
path.push_back(node -> val);
if (!(node -> left) &&!(node -> right) && sum == node -> val)
paths.push_back(path);
findPaths(node -> left, sum - node -> val, path, paths);
findPaths(node -> right, sum - node -> val, path, paths);
path.pop_back();
}
1 : Function Declaration
vector<vector<int>> pathSum(TreeNode* root, int sum) {
Declare the main function to find all paths summing to a target value.
2 : Vector Initialization
vector<vector<int>> paths;
Initialize a 2D vector to store all valid paths.
3 : Vector Initialization
vector<int> path;
Initialize a 1D vector to temporarily store the current path.
4 : Recursive Call
findPaths(root, sum, path, paths);
Invoke the helper function to find paths using backtracking.
5 : Return Statement
return paths;
Return the collection of all valid paths.
6 : Function Declaration
voidfindPaths(TreeNode* node, int sum, vector<int>& path, vector<vector<int>>& paths) {
Declare the helper function for recursive backtracking.
7 : Base Case
if (!node) return;
Base case: If the node is null, terminate the current recursive call.
8 : Push Operation
path.push_back(node -> val);
Add the current node's value to the path.
9 : Condition Evaluation
if (!(node -> left) &&!(node -> right) && sum == node -> val)
Check if the current node is a leaf and the remaining sum matches its value.
10 : Vector Insertion
paths.push_back(path);
Record the current path as a valid result.
11 : Recursive Call
findPaths(node -> left, sum - node -> val, path, paths);
Recursively explore the left subtree, updating the remaining sum.
12 : Recursive Call
findPaths(node -> right, sum - node -> val, path, paths);
Recursively explore the right subtree, updating the remaining sum.
13 : Pop Operation
path.pop_back();
Backtrack by removing the last node from the path.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: In the worst case, we will traverse all nodes in the tree. Therefore, the time complexity is O(n), where n is the number of nodes in the tree.
Best Case: O(h)
Worst Case: O(h)
Description: The space complexity is O(h), where h is the height of the tree, due to the recursive call stack. In the worst case (unbalanced tree), h can be equal to n.
