题目描述

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

给定二叉树和求和，找到所有根到叶路径，其中每个路径的总和等于给定的总和。

Note: A leaf is a node with no children.

注意：叶子是没有子节点的节点。

Example:

Given the below binary tree and sum = 22,

思路与实现

递归（DFS）

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> mid = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null)
            return res;
        dfs(root, 0, sum);
        
        return res;
    }

    private void dfs(TreeNode node, int sum, int target) {
        mid.add(node.val);
        
        if (node.left == null && node.right == null) {
            if (sum + node.val == target) 
                res.add(new ArrayList<>(mid));
        } else {
            if (node.left != null) 
                dfs(node.left, sum+node.val, target);
            
            if (node.right != null)
                dfs(node.right, sum+node.val, target);
        }
        
        mid.remove(mid.size()-1);
    }
}