→ Poshintow: 說人話 09/24 12:55
→ lopp54321010: 今天星期六 謝謝喔 09/24 12:56
推 Ericz7000: 有負的嗎？ 09/24 12:56
→ Rushia: 負的什麼 09/24 12:56
→ Ericz7000: 元素的值啊 09/24 12:57
→ Rushia: 有阿 不影響結果 09/24 12:58
推 Ericz7000: 喔我原本想說沒負的話 比目標大就不用找了 09/24 13:00
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