Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/113.html
113 Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
@tag-tree
Algorithm
To find the path in the previous question “Path Sum,” we still use DFS search, but the data structure is more complex and requires a two-dimensional list.
Whenever a new node is found during DFS search, it must be saved. Once a path is found, the path saved as a one-dimensional list is saved to the final result two-dimensional list. If DFS searches a child node and finds that it is not a path sum, it needs to be removed from the one-dimensional list when returning to the previous node.
Code
-
import java.util.ArrayList; import java.util.List; public class Path_Sum_II { public static void main(String[] args) { Path_Sum_II out = new Path_Sum_II(); Solution s = out.new Solution(); TreeNode root = new TreeNode(1); root.left = new TreeNode(2); s.pathSum(root, 3); } /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { List<List<Integer>> list = new ArrayList<>(); public List<List<Integer>> pathSum(TreeNode root, int sum) { if (root == null) { return list; } List<Integer> one = new ArrayList<>(); find(root, root, sum, one); return list; } private void find(TreeNode root, TreeNode originalRoot, int sum, List<Integer> one) { if (root == null) { return; } if (root.val == sum && root.left == null && root.right == null) { one.add(root.val); // list.add(one); // @note:@memorize: still, above pass a reference. should be a completely new list list.add(new ArrayList(one)); return; } one.add(root.val); find(root.left, root, sum - root.val, new ArrayList(one)); find(root.right, root, sum - root.val, new ArrayList(one)); } } } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private List<List<Integer>> ans = new ArrayList<>(); private List<Integer> t = new ArrayList<>(); public List<List<Integer>> pathSum(TreeNode root, int targetSum) { dfs(root, targetSum); return ans; } private void dfs(TreeNode root, int s) { if (root == null) { return; } s -= root.val; t.add(root.val); if (root.left == null && root.right == null && s == 0) { ans.add(new ArrayList<>(t)); } dfs(root.left, s); dfs(root.right, s); t.remove(t.size() - 1); } }
-
// OJ: https://leetcode.com/problems/path-sum-ii/ // Time: O(N) // Space: O(H) class Solution { vector<vector<int>> ans; vector<int> tmp; void dfs(TreeNode *root, int target) { if (!root) return; tmp.push_back(root->val); target -= root->val; if (target == 0 && !root->left && !root->right) ans.push_back(tmp); dfs(root->left, target); dfs(root->right, target); tmp.pop_back(); } public: vector<vector<int>> pathSum(TreeNode* root, int target) { dfs(root, target); return ans; } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]: def dfs(root, s): if root is None: return s += root.val t.append(root.val) if root.left is None and root.right is None and s == targetSum: ans.append(t[:]) dfs(root.left, s) dfs(root.right, s) t.pop() ans = [] t = [] dfs(root, 0) return ans ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def pathSum(self, root, sum): """ :type root: TreeNode :type sum: int :rtype: List[List[int]] """ def dfs(root, s, path, res): if root: path.append(root.val) s -= root.val left = dfs(root.left, s, path, res) right = dfs(root.right, s, path, res) if not left and not right and s == 0: res.append(path + []) path.pop() return True res = [] dfs(root, sum, [], res) return res
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func pathSum(root *TreeNode, targetSum int) (ans [][]int) { t := []int{} var dfs func(*TreeNode, int) dfs = func(root *TreeNode, s int) { if root == nil { return } s -= root.Val t = append(t, root.Val) if root.Left == nil && root.Right == nil && s == 0 { cp := make([]int, len(t)) copy(cp, t) ans = append(ans, cp) } dfs(root.Left, s) dfs(root.Right, s) t = t[:len(t)-1] } dfs(root, targetSum) return }
-
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} targetSum * @return {number[][]} */ var pathSum = function (root, targetSum) { const ans = []; const t = []; function dfs(root, s) { if (!root) return; s -= root.val; t.push(root.val); if (!root.left && !root.right && s == 0) ans.push([...t]); dfs(root.left, s); dfs(root.right, s); t.pop(); } dfs(root, targetSum); return ans; };
-
// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: Option<Rc<RefCell<TreeNode>>>, // pub right: Option<Rc<RefCell<TreeNode>>>, // } // // impl TreeNode { // #[inline] // pub fn new(val: i32) -> Self { // TreeNode { // val, // left: None, // right: None // } // } // } use std::rc::Rc; use std::cell::RefCell; impl Solution { fn dfs( root: Option<Rc<RefCell<TreeNode>>>, paths: &mut Vec<i32>, mut target_sum: i32, res: &mut Vec<Vec<i32>>, ) { if let Some(node) = root { let mut node = node.borrow_mut(); target_sum -= node.val; paths.push(node.val); if node.left.is_none() && node.right.is_none() { if target_sum == 0 { res.push(paths.clone()); } } else { if node.left.is_some() { Self::dfs(node.left.take(), paths, target_sum, res); } if node.right.is_some() { Self::dfs(node.right.take(), paths, target_sum, res); } } paths.pop(); } } pub fn path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> Vec<Vec<i32>> { let mut res = vec![]; let mut paths = vec![]; Self::dfs(root, &mut paths, target_sum, &mut res); res } }