Leetcode Path Sum II problem solution

YASH PAL,

In this Leetcode Path Sum II problem solution we have Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path’s sum equals targetSum. A leaf is a node with no children.

Leetcode Path Sum II problem solution

Problem solution in Python.

class Solution:
    def __init__(self):
        self.ret = []
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        

        l = []
        self.dfs(root,targetSum,[])
        return self.ret
   
    def dfs(self,root,targetSum,curr_path):

        if root is None:
            return 
        if root.left is None and root.right is None:
            if sum(curr_path) + root.val == targetSum:
                curr_path.append(root.val)
                self.ret.append(curr_path.copy())
                curr_path.pop()
            else:
                return

        else:
            curr_path.append(root.val)
            self.dfs(root.left,targetSum,curr_path)
            self.dfs(root.right,targetSum,curr_path)
            curr_path.pop()

Problem solution in Java.

class Solution {

List<List<Integer>> list=new ArrayList<>();
 public void pathSumHelper(TreeNode node, int target, ArrayList<Integer> ssf , int sum ) {
     
     if(node==null)
         return;
     
     if(node.left==null && node.right==null)
     {
            if(sum+node.val==target)
         {
          ssf.add(node.val);
          ArrayList temp=new ArrayList<>(ssf);   
          list.add(temp);
          ssf.remove(ssf.size()-1);
         }
         return;
         
     }
    
     ssf.add(node.val);
     pathSumHelper(node.left , target ,ssf , sum+node.val);
     pathSumHelper(node.right , target ,ssf , sum+node.val);
     ssf.remove(ssf.size()-1);
     
     return ;
         
     }

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    
    if(root==null)
        return new ArrayList<>();
    pathSumHelper(root,targetSum,new ArrayList<Integer>(),0);
   return list;
    
}
}

Problem solution in C++.

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        
        vector<vector<int>> res;
        
        vector<int> curr;
        
        dfs(root, sum, res, curr);
        
        return res;
        
    }
    
    void dfs(TreeNode* root, int sum, vector<vector<int>>& res, vector<int> curr){
        
        if(!root)
            return;
        
        curr.push_back(root->val);
        
        if(!root->left&&!root->right){
            if(sum-root->val==0)
                res.push_back(curr);
            return;
        }
        
        dfs(root->left,sum-root->val,res,curr);
        dfs(root->right,sum-root->val,res,curr);
        
    }
};

Problem solution in C.

class Solution {
public:
vector<vector<int>> result;
void bfs(TreeNode *t, int sum, vector<int> vec, int current)
{
	vec.push_back(t->val);
	if(t->left == NULL && t->right ==NULL && current + t->val == sum)
		result.push_back(vec);
		
	if(t->left != NULL)
		bfs(t->left, sum, vec, current + t->val);

	if(t->right != NULL)
		bfs(t->right, sum, vec, current + t->val);
};
vector<vector<int> > pathSum(TreeNode *root, int sum){
	if(root == NULL)
		return result;
	vector<int> vec;
	bfs(root, sum, vec, 0);
	return result;
}
};

coding problems