题解 | #牛的奶量统计II# java
牛的奶量统计II
https://www.nowcoder.com/practice/9c56daaded6b4ba3a9f93ce885dab764
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布尔型 */ boolean flag = false; public boolean hasPathSumII(TreeNode root, int targetSum) { if (root == null) { return false; } preorder(root, targetSum); return flag; } private void preorder(TreeNode root, int targetSum) { if (root == null || flag) { return; } dfs(root, targetSum); preorder(root.left, targetSum); preorder(root.right, targetSum); } private void dfs(TreeNode root, int targetSum) { if (root == null) { return; } targetSum -= root.val; if (targetSum == 0) { flag = true; return; } dfs(root.left, targetSum); dfs(root.right, targetSum); } }
代码使用的编程语言是Java。
该题考察的知识点是二叉树和深度优先搜索(DFS)。
代码的文字解释如下:
- 定义了一个
TreeNode
结构体,其中包含一个整型变量val
,以及左右子节点left
和right
。 - 定义了一个
Solution
类,其中包含一个布尔型方法hasPathSumII
,用于判断是否存在一条路径的节点值之和等于给定目标和targetSum
。 - 在
hasPathSumII
方法中,首先判断当前节点是否为空。如果为空,则返回false。 - 通过调用
preorder
方法进行先序遍历,并传入当前节点和目标和targetSum
作为参数。 - 在
preorder
方法中,首先判断当前节点是否为空或者已经找到满足条件的路径(即flag
为true)。如果是,则直接返回。 - 通过调用
dfs
方法递归地进行深度优先搜索,判断从当前节点开始是否存在满足条件的路径。 - 递归调用
preorder
方法分别处理当前节点的左子节点和右子节点。 - 在
dfs
方法中,首先判断当前节点是否为空。如果为空,则直接返回。 - 将当前节点的值从目标和
targetSum
中减去。 - 如果目标和
targetSum
等于0,则表示找到一条满足条件的路径,将flag
置为true,并返回。 - 递归调用
dfs
方法分别处理当前节点的左子节点和右子节点。