题解 | #牛的奶量统计II#
牛的奶量统计II
https://www.nowcoder.com/practice/9c56daaded6b4ba3a9f93ce885dab764
考察知识点: 递归、深度优先搜索
题目分析:
首先判断根节点是否为空。随后构建递归函数来判断当前节点是否满足路径和等于给定值。并且不断调用hasPathSumII函数来递归判断当前节点的子树中是否存在该路径。
所用编程语言: 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 hasPathSum(root, targetSum) ||
hasPathSumII(root.left, targetSum) ||
hasPathSumII(root.right, targetSum);
}
public boolean hasPathSum (TreeNode root, int sum) {
// write code here
if (root == null) {
return false;
}
return root.val == sum ||
hasPathSum(root.left, sum - root.val) ||
hasPathSum(root.right, sum - root.val);
}
}