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

描述

输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n

思路

当前的路径path要更新
当前的目标值expectNumber要迭代，减去当前节点的值
若当前节点是叶子节点，考虑是否满足路径的期待值，并考虑是否将路径添加到返回列表中
具体做法：

step 1：维护两个向量ret和path
step 2：编写递归函数dfs
step 3：递归函数内部要处理更新path，更新expectNumber，判断是否为叶子节点和判断是否要将path追加到ret末尾

代码

package mid.JZ34二叉树中和为某一值的路径2;

import java.util.ArrayList;
import java.util.LinkedList;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}

public class Solution {
    ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
        dfs(root,expectNumber);
        return ret;
    }

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

        dfs(root.left, expectNumber);
        dfs(root.right, expectNumber);

        path.removeLast();
    }
}