java 剑指offer之[数据结构 困难]JZ24 二叉树中和为某一值的路径

题目的链接在这里：https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca

• 题目大意
• 一、示意图
• 二、解题思路
• • DFS

dfs

代码如下：

import java.util.ArrayList;

import java.util.*;
public class Solution {
    public ArrayList> FindPath(TreeNode root,int expectNumber) {
        //需要DFS 把每一条边都进行判断
       // Stack stack=new Stack<>();
        ArrayList> res=new ArrayList<>();
        ArrayList arrayList=new ArrayList<>();
        ArrayList arrayList1=new ArrayList<>();
        //不能排除负数
        if(root==null)
            return res;
        //然后依次进行判断
        //还有一些边界判断
        if(root.val==expectNumber){
            arrayList.add(root.val);
            res.add(arrayList);
            return res;
        }
        int num=root.val;
        arrayList.add(root.val);
        arrayList1.add(root.val);
       // stack.add(root);
        //然后进行判断
        if(root.left!=null){
            //对左子树进行dfs
            dfs(root.left,expectNumber,arrayList,num,res);
        }
        //这里可能存在覆盖的问题
        if(root.right!=null){
            dfs(root.right,expectNumber,arrayList1,num,res);
        }
        return res;
    }
    //dfs回退的覆盖问题
    private void dfs(TreeNode root, int expectNumber,  ArrayList arrayList, int num, ArrayList> res) {
        if(root==null)
            return;
        //然后先进行判断
        //要先进行更新 这些if是需要判断的
    
        //不然的话 也是需要遍历的
        //先判断会不会超出范围 expectNumber-num是还差的值
        //有负数就离谱
      
        //这里还有个细节是 必须要到根节点
        if((expectNumber-num)==root.val&&(root.left==null)&&(root.right==null)){
            //刚好相等的话 那就直接开始返回
            arrayList.add(root.val);
            res.add(arrayList);
            return;
        }
      
        //不然的话 就放进去 然后进行更新
        num+=root.val;
        arrayList.add(root.val);
        //是不是还需要再加一个判断
        //然后进行判断
        //这里就不判断了
      
        dfs(root.left,expectNumber,new ArrayList<>(arrayList),num,res);
        dfs(root.right,expectNumber,new ArrayList<>(arrayList),num,res);
    }
}