题解 | 二叉树中和为某一值的路径(二)

import java.util.*;

public class Solution {

    // 找出二叉树中结点值的和为expectNumber的所有路径
    // 该题路径定义为从根节点一直到叶子结点，要用dfs
    ArrayList<ArrayList<Integer>> res_list = new ArrayList<>();
    // 双向链表，可以从尾部remove，也可以new ArrayList<>(path)转为链表
    LinkedList<Integer> list = new LinkedList<>();

    public ArrayList<ArrayList<Integer>> FindPath (TreeNode root, int target) {
        // write code here

        dfs(root,target);

        return res_list;
    }

    public void dfs(TreeNode root, int number) {
        if (root == null) return;
        list.add(root.val);
        if (root.left == null && root.right == null && number - root.val == 0) {
            res_list.add(new ArrayList<>(list));
        }
        dfs(root.left,number - root.val);
        dfs(root.right,number - root.val);
        list.removeLast();
    }
}