Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
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: []
Constraints:
[0, 5000]
.-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> list = new ArrayList<>();
if (root == null) return list;
List<Integer> path = new ArrayList<>();
Stack<TreeNode> s = new Stack<>();
// sum along the current path
int pathSum = 0;
TreeNode prev = null;
TreeNode curr = root;
while (curr != null || !s.isEmpty()){
// go down all the way to the left leaf node
// add all the left nodes to the stack
while (curr != null){
s.push(curr);
// record the current path
path.add(curr.val);
// record the current sum along the current path
pathSum += curr.val;
curr = curr.left;
}
// check left leaf node's right subtree
// or check if it is not from the right subtree
// why peek here?
// because if it has right subtree, we don't need to push it back
curr = s.peek();
if (curr.right != null && curr.right != prev){
curr = curr.right;
continue; // back to the outer while loop
}
// check leaf
if (curr.left == null && curr.right == null && pathSum == sum){
list.add(new ArrayList<Integer>(path));
// why do we need new arraylist here?
// if we are using the same path variable path
// path will be cleared after the traversal
}
// pop out the current value
s.pop();
prev = curr;
// subtract current node's val from path sum
pathSum -= curr.val;
// as this current node is done, remove it from the current path
path.remove(path.size()-1);
// reset current node to null, so check the next item from the stack
curr = null;
}
return list;
}
class Solution {
public:
void getAllPaths(TreeNode *root,int targetSum,vector<int> temp,vector<vector<int>> &ans)
{
if(!root)
return;
if(!root->left and !root->right and targetSum == root->val)
{
temp.push_back(root->val);
ans.push_back(temp);
return;
}
temp.push_back(root->val);
getAllPaths(root->left,targetSum-root->val,temp,ans);
getAllPaths(root->right,targetSum-root->val,temp,ans);
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum)
{
vector<vector<int>> ans;
getAllPaths(root,targetSum,{},ans);
return ans;
}
};
class Solution:
def pathSum(self, root, sm):
def dfs(node, sm):
if not node: return []
if not node.left and not node.right and sm == node.val:
return [[node.val]]
lft = dfs(node.left, sm - node.val)
rgh = dfs(node.right, sm - node.val)
return [cand + [node.val] for cand in lft + rgh]
return [s[::-1] for s in dfs(root, sm)]
In our experience, we suggest you solve this Path Sum II LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Path Sum II LeetCode Solution
I hope this Path Sum II LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More Coding Solutions >>