Here, We see Path Sum II LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Path Sum II LeetCode Solution
Table of Contents
Problem Statement
Given the root
of a binary tree and an integer targetSum
, return all root-to-leaf paths where the sum of the node values in the path equals targetSum
. Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum: 5 + 4 + 11 + 2 = 22 5 + 8 + 4 + 5 = 22
Example 2:
Input: root = [1,2,3], targetSum = 5
Output: []
Example 3:
Input: root = [1,2], targetSum = 0
Output: []
Path Sum II LeetCode Solution C++
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int> > paths;
vector<int> path;
findPaths(root, targetSum, path, paths);
return paths;
}
private:
void findPaths(TreeNode* node, int sum, vector<int>& path, vector<vector<int> >& paths) {
if (!node) return;
path.push_back(node -> val);
if (!(node -> left) && !(node -> right) && sum == node -> val)
paths.push_back(path);
findPaths(node -> left, sum - node -> val, path, paths);
findPaths(node -> right, sum - node -> val, path, paths);
path.pop_back();
}
};
Code language: PHP (php)
Path Sum II LeetCode Solution Java
class Solution {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
private void dfs(TreeNode node, List<Integer> path, int remainingSum) {
if (node == null) return;
path.add(node.val);
if (node.left == null && node.right == null && remainingSum == node.val) ans.add(new ArrayList<>(path));
this.dfs(node.left, path, remainingSum - node.val);
this.dfs(node.right, path, remainingSum - node.val);
path.remove(path.size() - 1);
}
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<Integer> path = new ArrayList<Integer>();
dfs(root, path, targetSum);
return ans;
}
}
Code language: PHP (php)
Path Sum II Solution JavaScript
var pathSum = function(root, targetSum) {
function dfs(node, curPath, curTarget){
if( node == null ){
return;
}
curPath.push( node.val );
curTarget -= node.val;
if( node.left == null && node.right == null && curTarget == 0 ){
answer.push( curPath.slice() );
curPath.pop();
return;
}
dfs( node.left, curPath, curTarget );
dfs( node.right, curPath, curTarget );
curPath.pop();
return;
}
answer = [];
dfs(root, [], targetSum);
return answer;
};
Code language: JavaScript (javascript)
Path Sum II Solution Python
class Solution:
def dfs(self, root, path, ans, remainingSum):
if not root:
return
path.append(root.val)
if not root.left and not root.right and remainingSum == root.val:
ans.append(list(path))
self.dfs(root.left, path, ans, remainingSum - root.val)
self.dfs(root.right, path, ans, remainingSum - root.val)
path.pop()
def pathSum(self, root, targetSum):
ans = []
self.dfs(root, [], ans, targetSum)
return ans