26.路径总和II

题目描述

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

解题思路

深度优先算法

我们可以采用深度优先搜索的方式，枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点，且此时路径和恰为目标和时，就找到了一条满足条件的路径。

Code：

class Solution{
    List<List<Integer>> ans = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root,int sum){
        dfs(root,sum);
        return ans;
    }

    public void dfs(TreeNode root,int sum){
        if(root == null){
            return;
        }
        path.add(root.val);
        sum -= root.val;
        if(root.left == null && root.right == null && sum == 0){
            ans.add(new LinkedList<Integer>(path));
        }
        dfs(root.left,sum);
        dfs(root.right,sum);
        path.removeLast();
    }
}