题解 | #牛的奶量统计#
牛的奶量统计
https://www.nowcoder.com/practice/213c039668804add9513bbee31370248
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 hasPathSum (TreeNode root, int targetSum) { // write code here if (root == null) return false; // 如果根节点是叶子节点,判断它的值是否等于目标值 这个条件很容易被忽略 if (root.left == null && root.right == null) return root.val == targetSum; // 递归判断左右子树是否有满足条件的路径,只要有一个为 true 就返回 true return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); } }
本题知识点分析:
二叉树的遍历,深度优先搜索,递归
本题解题思路分析:
这道题的本质就是遍历所有所有根节点到叶子节点的路径,找出符合targetsum等于根节点到叶子节点的路径上所有节点值的和,换个思考角度,我们每遍历一层就将targetsum-root.val的值传递下去,直到传到某一个叶子节点符合targetsum-root.val=0;则可返回true,否则返回false。因为根节点将targetsum-root.val传给左右子树,而其左右子树继续同样的操作,为此我们可以使用递归来完成这些操作。