路径总和Ⅱ

Leetcode题目描述

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

          5
         / 
        4   8
       /   / 
      11  13  4
     /      / 
    7    2  5   1

返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

回溯算法

仍然是回溯算法的标准解答方式，注意在List<List<>> res 这种类型的List.add()时注意添加存储空间new ArrayList<>()

• 还有注意判断末尾结点是否是叶子结点

回溯Demo

class Solution {
    private int t1 = 0;

    public void dfs(TreeNode root, int sum, List<Integer> t2, List<List<Integer>> ans){
        if (root == null ) return;
        sum = sum + root.val;
        t2.add(root.val);
        if (root.left != null ) dfs(root.left, sum ,t2, ans);
        if (root.right != null ) dfs(root.right, sum, t2, ans);

        if (root.right == null && root.left == null && sum == t1){
            ans.add(new ArrayList<>(t2));
        }

        t2.remove(t2.size() - 1);
        return;
    }

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<Integer> t2 = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<>();
        t1 = sum;
        dfs(root,0, t2, ans);
        return ans;
    }
}