grid47 Exploring patterns and algorithms
Sep 24, 2024
6 min read
Solution to LeetCode 437: Path Sum III Problem
You are given the root of a binary tree and an integer targetSum. Your task is to count the total number of paths in the tree where the sum of node values along the path equals targetSum. The path does not need to start or end at the root or a leaf, but it must go downwards (from parent to child nodes).
Problem
Approach
Steps
Complexity
Input: The input consists of a binary tree represented by the root node and an integer targetSum.
• Explanation: The three paths that sum to 8 are: `5 -> 3`, `5 -> 2 -> 1`, and `-3 -> 11`.
Approach: The approach uses DFS to explore all possible paths in the binary tree and checks whether the sum of the values along the path equals targetSum.
Observations:
• DFS is a suitable approach to explore all potential paths in a binary tree.
• We need to perform DFS starting from each node to explore all paths from that node downwards.
Steps:
• 1. Perform DFS for each node in the tree.
• 2. At each node, recursively calculate all paths starting from that node that sum to targetSum.
• 3. Track and count the paths that meet the targetSum condition.
Empty Inputs:
• If the tree is empty (i.e., root is null), return 0.
Large Inputs:
• Ensure that the algorithm works efficiently for trees with up to 1000 nodes.
Special Values:
• If targetSum is 0, consider paths where the sum of values along the path equals 0.
Constraints:
• Handle large integer values within the specified range of [-10^9, 10^9].
classSolution {
int cnt =0;
public:int pathSum(TreeNode* root, int sum) {
dfs(root, sum);
return cnt;
}
voiddfs(TreeNode* root, long sum) {
if(root ==NULL) return;
test(root, sum);
dfs(root->left, sum);
dfs(root->right, sum);
}
voidtest(TreeNode* root, long sum) {
if (root ==NULL) return;
if (root->val == sum ) cnt++;
test(root->left, sum - root->val);
test(root->right, sum - root->val);
}
1 : Class Declaration
classSolution {
Declares the Solution class where the methods and variables are defined.
2 : Variable Declaration
int cnt =0;
Initializes a counter to store the number of valid paths with the desired sum.
3 : Access Specifier
public:
Defines the public section of the class to include accessible methods.
4 : Function Declarations And Calls
intpathSum(TreeNode* root, int sum) {
Declares the main function to calculate the total number of paths that sum to a target value.
5 : Recursive Call
dfs(root, sum);
Calls the helper function 'dfs' to traverse the tree starting from the root node.
6 : Return At End
return cnt;
Returns the total count of paths with the desired sum.
7 : Recursive Function Definition
voiddfs(TreeNode* root, long sum) {
Defines the DFS function to traverse the binary tree and test each node for valid paths.
8 : Base Condition
if(root ==NULL) return;
Checks if the current node is null to terminate the recursion.
9 : Function Call
test(root, sum);
Calls the 'test' function to check paths starting from the current node.
10 : Recursive Call
dfs(root->left, sum);
Recursively calls 'dfs' for the left child of the current node.
11 : Recursive Call
dfs(root->right, sum);
Recursively calls 'dfs' for the right child of the current node.
12 : Recursive Function Definition
voidtest(TreeNode* root, long sum) {
Defines the 'test' function to check all paths starting at the current node for the target sum.
13 : Base Condition
if (root ==NULL) return;
Terminates the recursion when the node is null.
14 : Conditional Checks
if (root->val == sum ) cnt++;
Increments the counter if the current node value equals the remaining sum.
15 : Recursive Call
test(root->left, sum - root->val);
Recursively checks the left subtree for paths with the updated remaining sum.
16 : Recursive Call
test(root->right, sum - root->val);
Recursively checks the right subtree for paths with the updated remaining sum.
Best Case: O(N), where N is the number of nodes in the tree, if all paths meet the targetSum immediately.
Average Case: O(N^2), where N is the number of nodes, due to the DFS for each node and the exploration of all paths.
Worst Case: O(N^2), where N is the number of nodes, as every node can lead to a path traversal that checks all remaining nodes.
Description: The time complexity involves performing DFS and recursively checking all paths from each node, leading to an overall complexity of O(N^2).
Best Case: O(H), for the recursive stack space.
Worst Case: O(H), where H is the height of the tree, due to the recursion stack in DFS.
Description: The space complexity is determined by the recursion depth of the DFS traversal.
