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);
    }
}