题解 | #牛群特殊路径的数量#
牛群特殊路径的数量
https://www.nowcoder.com/practice/1c0f95d8396a432db07945d8fe51a4f5
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 sum int整型 * @return int整型 */ int ans = 0; /** * 计算路径和等于给定值的路径数量 * * @param root 二叉树的根节点 * @param sum 给定的目标和 * @return 路径和等于给定值的路径数量 */ public int pathSum(TreeNode root, int sum) { if (root == null) return 0; preorder(root, sum); return ans; } /** * 先序遍历二叉树,在每个节点处调用dfs方法计算路径和等于给定值的路径数量 * * @param root 当前节点 * @param sum 从根节点到当前节点的路径和 */ private void preorder(TreeNode root, int sum) { if (root == null) return; dfs(root, sum); preorder(root.left, sum); preorder(root.right, sum); } /** * 深度优先搜索,计算从当前节点出发路径和等于给定值的路径数量 * * @param root 当前节点 * @param sum 从根节点到当前节点的路径和 */ private void dfs(TreeNode root, int sum) { if (root == null) return; sum -= root.val; if (sum == 0) { ans++; } dfs(root.left, sum); dfs(root.right, sum); } }
代码使用的编程语言是Java。
该代码考察的知识点包括:
- 二叉树的先序遍历
- 二叉树的深度优先搜索(DFS)
- 递归算法