Re: [閒聊] 每日LeetCode
113. Path Sum II
給予一個二元樹和一個target，求出根節點到葉子節點元素總和為target的所有Path。
Example：
https://assets.leetcode.com/uploads/2021/01/18/pathsumii1.jpg
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
思路：
1.用回溯法解。
2.利用一個List紀錄當前走訪過的元素，若路徑和等於target且是葉子節點時將解加入
解集合。
JavaCode：
class Solution {
private List<List<Integer>> res;
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
res = new ArrayList<>();
DFS(root, new ArrayList<>(), targetSum, 0);
return res;
}
private void DFS(TreeNode root, List<Integer> curr, int target, int sum) {
if(root == null)
return;
sum += root.val;
curr.add(root.val);
if(sum == target && root.left == null && root.right == null)
res.add(new ArrayList<>(curr));
DFS(root.left, curr, target, sum);
DFS(root.right, curr, target, sum);
curr.remove(curr.size() - 1);
}
}
二元樹題目 = 溫柔善良
--
https://i.imgur.com/bFRiqA3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.165.253.177 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1663995294.A.343.html
→
09/24 12:55,
1年前
, 1F
09/24 12:55, 1F
→
09/24 12:56,
1年前
, 2F
09/24 12:56, 2F
推
09/24 12:56,
1年前
, 3F
09/24 12:56, 3F
→
09/24 12:56,
1年前
, 4F
09/24 12:56, 4F
→
09/24 12:57,
1年前
, 5F
09/24 12:57, 5F
→
09/24 12:58,
1年前
, 6F
09/24 12:58, 6F
推
09/24 13:00,
1年前
, 7F
09/24 13:00, 7F
討論串 (同標題文章)
完整討論串 (本文為第 9 之 719 篇)：
閒聊
1
3