题解 | #二叉树中和为某一值的路径(三)#

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 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */

    int res = 0; 
    public int FindPath (TreeNode root, int sum) {
        if(root == null) return res;
        reverse(root , sum);
        FindPath(root.left,sum);
        FindPath(root.right,sum);
        return res;
    }

    private void reverse(TreeNode root, int sum) {
        if(root != null){
            if(root.val == sum){
                res++;
            }
            reverse(root.left,sum - root.val);
            reverse(root.right,sum - root.val);
        }
    }
}

思路：

使用双递归。一开始没有想到还有双递归的操作，看了一下官方回答醍醐灌顶，因为此题求的任意路径等于sum的个数，单靠一个递归输入根节点计算符合的路径不可行。把每个节点当作根节点，递归一次对sum进行减操作来判定。