Sponsored
Sponsored
This approach uses a recursive DFS strategy to navigate from the root to each leaf, calculating the cumulative sum along the path. If we find a path where the cumulative sum equals the targetSum at a leaf node, we return true. Otherwise, we continue exploring other paths. In case we exhaust all paths without finding a valid path, we return false.
Time Complexity: O(N), where N is the number of nodes in the tree, as we have to visit each node.
Space Complexity: O(H), where H is the height of the tree due to the recursion stack.
1#include <stdbool.h>
2
3typedef struct TreeNode {
4 int val;
5 struct TreeNode *left;
6 struct TreeNode *right;
7} TreeNode;
8
9bool hasPathSum(TreeNode* root, int targetSum) {
10 if (!root) return false;
11 if (!root->left && !root->right) return root->val == targetSum;
12 targetSum -= root->val;
13 return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
14}The C implementation uses a recursive function similar to other languages. It operates by checking if the root is null before proceeding to adjust the target sum and exploring left and right children recursively.
In contrast to the recursive method, this approach utilizes an explicit stack to iteratively perform DFS, tracking the cumulative sum along each path. Nodes are pushed onto the stack with their cumulative sums traversed thus far, effectively replacing the recursion stack with an explicit stack to manage state manually. This can help in environments with limited recursion support.
Time Complexity: O(N), examining each node iteratively.
Space Complexity: O(N), as the stack could store up to all nodes in the worst scenario (e.g., a path-heavy tree with a single path).
1
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if (!root) return false;
std::stack<TreeNode*> nodes;
std::stack<int> sums;
nodes.push(root);
sums.push(root->val);
while (!nodes.empty()) {
TreeNode* currentNode = nodes.top(); nodes.pop();
int currentSum = sums.top(); sums.pop();
if (!currentNode->left && !currentNode->right && currentSum == targetSum) {
return true;
}
if (currentNode->right) {
nodes.push(currentNode->right);
sums.push(currentSum + currentNode->right->val);
}
if (currentNode->left) {
nodes.push(currentNode->left);
sums.push(currentSum + currentNode->left->val);
}
}
return false;
}
};The C++ implementation similarly uses stacks for managing traversal, keeping track of each path sum actively without recursion. Stacks provide storage for nodes and path sums to enable iterative depth-first exploration, culminating checks at leaf nodes.