JZ24 二叉树中和为某一值的路径

• 思路：该题是求解二叉树中一条路径中的的值，所以可以利用DFS（深度优先搜索）进行处理，利用回溯法进行深度查找
• 时间：2021年8月5号
• 扩展：求解一条线路上的和，加入到集合ArrayList<integer>()中</integer>

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        //DFS深度优先搜索
        int sum = 0;

        DFSTree(root, target, sum, new ArrayList<Integer>());

        return ans;
    }
    //方法一：
    public void DFSTree(TreeNode root, int target, int sum, ArrayList<Integer> ls) {
        if (root == null)
            return;
        ls.add(root.val);
        sum += root.val;
        if (sum == target && root.left == null && root.right == null) {
            ans.add(new ArrayList<Integer>(ls));
        }

        DFSTree(root.left, target, sum, ls);
        DFSTree(root.right, target, sum, ls);
        ls.remove(ls.size() - 1);

    }

    //方法二：
//     public void DFSTree(TreeNode root, int target, ArrayList<Integer> ls) {
//         if (root == null)
//             return;
//         target -= root.val;
//         ls.add(root.val);

//         if (target == 0 && root.left == null && root.right == null) {
// //             System.out.println(ls);
//             ans.add(new ArrayList<Integer>(ls));
// //             System.out.println("第" + i++ + "次：" + ans);
//         }

//         DFSTree(root.left, target, ls);
//         DFSTree(root.right, target, ls);
//         ls.remove(ls.size() - 1);
//     }
}