D
DevExCode

LeetCode 112: Path Sum Solution

Master LeetCode problem 112 (Path Sum), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To solve this problem, we can perform a depth-first search (DFS) traversal of the binary tree while keeping track of the current path sum from the root to the current node. When we reach a leaf node, we check if the current path sum equals the target sum. If it does, we return true. If not, we continue the traversal.

Algorithm:

  1. Initialize a boolean flag to track whether a valid path sum is found.
  2. Implement a recursive DFS function that takes the current node, current path sum, and target sum as parameters.
  3. If the current node is null, return false.
  4. Update the current path sum by adding the value of the current node.
  5. If the current node is a leaf node, check if the current path sum equals the target sum. If it does, set the flag to true.
  6. Recursively call the function for the left and right child nodes with the updated path sum.
  7. Return the flag at the end of the function.

Time Complexity:

The time complexity of this approach is O(n), where n is the number of nodes in the binary tree.

Space Complexity:

The space complexity is O(h), where h is the height of the binary tree. In the worst case of a skewed tree, the space complexity can be O(n).

Solution Code

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        
        return hasPathSumHelper(root, 0, targetSum);
    }
    
    private boolean hasPathSumHelper(TreeNode node, int currentSum, int targetSum) {
        if (node == null) {
            return false;
        }
        
        currentSum += node.val;
        
        if (node.left == null && node.right == null) {
            return currentSum == targetSum;
        }
        
        return hasPathSumHelper(node.left, currentSum, targetSum) || hasPathSumHelper(node.right, currentSum, targetSum);
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 112 (Path Sum)?

This page provides optimized solutions for LeetCode problem 112 (Path Sum) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 112 (Path Sum)?

The time complexity for LeetCode 112 (Path Sum) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 112 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 112 in Java, C++, or Python.

Back to LeetCode Solutions