题解 | #牛的奶量统计II#

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 targetSum int整型
     * @return bool布尔型
     */
    public boolean hasPathSumII (TreeNode root, int targetSum) {
        // write code here
          if(root == null) return false;
        return fun(root,targetSum);
    }
 
    public boolean fun(TreeNode root,int targetSum){
        boolean ans = fun2(root,0,targetSum);
        if(root.left != null){
            ans = ans || fun(root.left,targetSum);
        }
        if(root.right != null){
            ans = ans || fun(root.right,targetSum);
        }
        return ans;
    }
 
    public boolean fun2(TreeNode root,int preSum,int targetSum){
        int num = root.val + preSum;
        if(num == targetSum) return true;
        if(num > targetSum) return false;
        boolean ans = false;
        if(root.left != null) {
            ans = ans || fun2(root.left,num,targetSum);
        }
        if(root.right != null){
            ans = ans || fun2(root.right,num,targetSum);
        }
        return ans;
    }
}

知识点:

树，深度遍历

解题思路:

任意节点到任意节点的值等于targetNum与根节点到叶子节点的值等于targetNum的区别是，前者需要判断这颗树任意节点到子节点的值累加是否等于targetNum。

我们可以分解成某个节点到子节点累加值是否等于targetNum，当累加大于了targetNum，就再继续判断下一个节点的累加。

因此需要使用两个递归，一个递归是递归树的全部节点，子递归是递归某个节点到子节点判断累加。