题解 | #牛群特殊路径的数量#
牛群特殊路径的数量
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整型 */ private static Integer count = 0; public int pathSum (TreeNode root, int sum) { search(root, sum); return count; } public void search(TreeNode root, int sum) { if (root == null) { return; } dfs(root, sum); search(root.left, sum); search(root.right, sum); } public void dfs(TreeNode root, int sum) { if (root == null) { return; } sum -= root.val; if (sum == 0) { count++; } dfs(root.left, sum); dfs(root.right, sum); } }
本题知识点分析:
1.二叉树前序遍历;
2.深度优先搜索;
3.数学模拟;
本题解题思路分析:
1.利用二叉树前序遍历
2.DFS深度优先搜索去找路径求和为sum的路径,如果sum为0表示找到一条路径,count++;
3.分别遍历左子树和右子树,再去DFS,最终将count返回即可;