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

题目

给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。
1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点
2.总节点数目为n
3.保证最后返回的路径个数在整形范围内(即路径个数小于231-1)

方法 非递归层次遍历

思路

算法实现

既然要找所有路径上节点和等于目标值的路径个数，那我们肯定先找这样的路径起点啊，但是我们不知道起点究竟在哪里，
而且任意节点都有可能是起点，那我们就前序遍历二叉树的所有节点，每个节点都可以作为一次起点，即子树的根节点。
具体做法：
    step 1：每次将原树中遇到的节点作为子树的根节点送入dfs函数中查找有无路径，如果该节点为空则返回。
    step 2：然后递归遍历这棵树每个节点，每个节点都需要这样操作。
    step 3：在dfs函数中，也是往下递归，遇到一个节点就将sum减去节点值再往下。
    step 4：剩余的sum等于当前节点值则找到一种情况。

代码

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

import java.util.*;

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

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param root TreeNode类
     * @param sum  int整型
     * @return int整型
     */
    private int res = 0;
    public int FindPath(TreeNode root, int sum) {
        // write code here
        if (root == null) return res;

        //查询以某结点为根的路径数
        dfs(root, sum);

        //以其子结点为新根
        FindPath(root.left, sum);
        FindPath(root.right, sum);
        return res;
    }
    public void dfs (TreeNode root, int sum) {
        if (root == null) return;
        //符合目标。res++
        if (sum == root.val)  res++;

        //子节点继续查找
        dfs(root.left, sum - root.val);
        dfs(root.right, sum - root.val);
    }
}