解法一：深度优先搜索

深搜，没啥特别的。

  1. import java.util.LinkedList;
  2. import java.util.List;
  4. /**
  5.  * Definition for a binary tree node.
  6.  * public class TreeNode {
  7.  * int val;
  8.  * TreeNode left;
  9.  * TreeNode right;
  10.  * TreeNode(int x) { val = x; }
  11.  * }
  12.  */
  14. class Solution {
  15.     List<List<Integer>> ans;
  17.     public List<List<Integer>> pathSum(TreeNode root, int sum) {
  18.         ans = new LinkedList<>();
  19.         dfs(root, sum, new LinkedList<>());
  20.         return ans;
  21.     }
  23.     private void dfs(TreeNode root, final int sum, List<Integer> nums) {
  24.         if (root == null) {
  25.             return;
  26.         }
  27.         nums.add(root.val);
  28.         if ((root.left == null) && (root.right == null)) {
  29.             int temp = 0;
  30.             for (int i : nums) {
  31.                 temp += i;
  32.             }
  33.             if (temp == sum) {
  34.                 ans.add(new LinkedList<>(nums));
  35.             }
  36.             nums.remove(nums.size() - 1);
  37.             return;
  38.         }
  40.         dfs(root.left, sum, nums);
  41.         dfs(root.right, sum, nums);
  42.         nums.remove(nums.size() - 1);
  43.     }
  44. }