剑指 Offer 34. 二叉树中和为某一值的路径

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

思路

dfs

代码

class Solution {
    private List> ans;
    public List> pathSum(TreeNode root, int target) {
        ans = new ArrayList>();
        if (root == null) return ans;
        List path = new ArrayList();
        path.add(root.val);
        dfs(root, target, root.val, path);
        return ans;
    }

    public void dfs(TreeNode root, int target, int sum, List path) {
        if (root.left == null && root.right == null) {
            if (sum == target) {
                ans.add(new ArrayList(path));
            }
            return;
        }
        if (root.left != null) {
            path.add(root.left.val);
            dfs(root.left, target, sum + root.left.val, path);
            path.remove(path.size() - 1);
        }
        if (root.right != null) {
            path.add(root.right.val);
            dfs(root.right, target, sum + root.right.val, path);
            path.remove(path.size() - 1);
        }
    }
}