Problem 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.
Key Insights
- The problem requires finding a path from the root to a leaf node where the sum of the node values equals a given target.
- A leaf node is defined as a node with no children.
- Depth-First Search (DFS) is a suitable algorithm for traversing the tree to explore all possible paths.
- The base cases include checking if the tree is empty or if a node is a leaf.
Space and Time Complexity
Time Complexity: O(N), where N is the number of nodes in the tree, as we may need to visit each node once. Space Complexity: O(H), where H is the height of the tree, due to the recursion stack in the DFS approach.
Solution
The solution employs a Depth-First Search (DFS) strategy, traversing the binary tree from the root to the leaves. During the traversal, we maintain a current sum of the values from the root to the current node. When we reach a leaf node, we check if the current sum equals the targetSum. If it does, we return true; otherwise, we continue exploring other paths. If we finish exploring all paths without finding a valid one, we return false.