剑指offer18 JZ34 二叉树中和为某一值的路径(二)

深度优先搜索（dfs）

深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。

思路：

我们从根节点开始向左右子树进行递归，递归函数中需要处理的是：

当前的路径path要更新

当前的目标值expectNumber要迭代，减去当前节点的值

若当前节点是叶子节点，考虑是否满足路径的期待值，并考虑是否将路径添加到返回列表中

具体做法：

step 1：维护两个向量res和path

step 2：编写递归函数dfs

step 3：递归函数内部要处理更新path，更新expectNumber，判断是否为叶子节点和判断是否要将path追加到ret末尾

import java.util.*;
/**
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>> res=new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
     
        dfs(root,expectNumber);
        return res;
    }
    public void dfs(TreeNode cur,int sum){
        //当前节点为空 结束本次
        if(cur==null){
            return ;
        }
        //保存每个路过的路径
        path.add(cur.val);
        sum-=cur.val;
        if(cur.left==null&& cur.right==null && sum==0 ){
            //为叶子节点 且找到了目标值
            res.add(new ArrayList<>(path));
        }
        //递归左节点
        dfs(cur.left,sum);
        //递归右节点
        dfs(cur.right,sum);
        //回溯
        path.removeLast();
    }
}