Path Sum Leetcode Solution

In this post, you will know how to solve the Path Sum Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.

Problem

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.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

Path Sum Leetcode Solutions in Python

class Solution:
  def hasPathSum(self, root: TreeNode, summ: int) -> bool:
    if not root:
      return False
    if root.val == summ and not root.left and not root.right:
      return True
    return self.hasPathSum(root.left, summ - root.val) or \
        self.hasPathSum(root.right, summ - root.val)

Path Sum Leetcode Solutions in CPP

class Solution {
 public:
  bool hasPathSum(TreeNode* root, int sum) {
    if (root == nullptr)
      return false;
    if (root->val == sum && root->left == nullptr && root->right == nullptr)
      return true;
    return hasPathSum(root->left, sum - root->val) ||
           hasPathSum(root->right, sum - root->val);
  }
};

Path Sum Leetcode Solutions in Java

class Solution {
  public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null)
      return false;
    if (root.val == sum && root.left == null && root.right == null)
      return true;
    return hasPathSum(root.left, sum - root.val) ||
           hasPathSum(root.right, sum - root.val);
  }
}

Note: This problem Path Sum Tree is generated by Leetcode but the solution is provided by  Brokenprogrammers. This tutorial is only for Educational and Learning purposes.

Next: Minimum Depth of Binary Tree Leetcode Solution