題目鏈接

遞歸

本題遞歸需要遍歷整棵樹，所以遞歸沒有返回值

/*** 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 {public void traversal(TreeNode root, int count, List<List<Integer>> res, List<Integer> res1){res1.add(root.val);// 葉子節點且找到和為targetSum的路徑if(root.left == null && root.right == null && count - root.val == 0){res.add(new ArrayList<>(res1));return;}// 葉子節點，和不為 targetsum，返回if(root.left == null && root.right == null){return;}if(root.left != null){traversal(root.left, count - root.val, res, res1);// 回溯res1.removeLast();}if(root.right != null){traversal(root.right, count - root.val, res, res1);// 回溯res1.removeLast();}}public List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<List<Integer>> res = new  LinkedList<List<Integer>>();List<Integer> res1 = new LinkedList<Integer>();if(root == null){return res;}traversal(root,targetSum,res,res1);return res;}
}

回顧本題時，請結合Leetcode112路徑總和