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

题目考察的知识点

考察二叉树深度优先搜索

题目解答方法的文字分析

需要明白这道题目的意思，并不要求一定从根节点开始，可以从中间节点开始。递归调用函数检查根节点以及两个子树节点即可。具体细节参看下方代码。

本题解析所用的编程语言

使用Java代码解答

完整且正确的编程代码

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 dfs(root,targetSum)||hasPathSumII(root.left,targetSum)||hasPathSumII(root.right,targetSum);
    }

    public boolean dfs(TreeNode root, int targetSum){
        if(root==null) return false; //节点为null
        if(root.left==null&&root.right==null) return root.val==targetSum; //叶子节点判断
        targetSum -= root.val;
        return dfs(root.left,targetSum)||dfs(root.right,targetSum);
    }
}