首页 > 路径数目
开通博客写题解
头像 leaves0924
发表于 2021-09-12 16:37:09
题目描述 给出一颗以1为根的树，树上节点的值只为1或者0，在最多经过两个值为1的节点的情况下，有多少条到达叶节点的路径？输入第一个参数为 n ，(1≤n≤100,000)第二个参数为大小为 n-1 的点对 的集合，其中 表示结点 ui 与结点 vi之间有一条边， , 第三个参数为大小为 n 的 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 xqxls
发表于 2021-09-05 23:27:50
题意整理 给定一颗有n个节点的树，每个节点的值初始为0或1。 求有多少条从根节点到叶子节点的路径（要求路径上节点值得累加和小于等于2）。 方法一（DFS） 1.解题思路 首先建立邻接表，用于访问某个节点的所有子节点。 从根节点开始递归，并且初始化一个num为2，每到一个节点，num减去对应节点 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 东溪看水
发表于 2020-08-05 14:44:03
题目 牛牛来到训练场里闯关，他的宝剑的耐久度降到了 2，这意味着牛牛最多只能打倒 2 只怪兽，否则将会被淘汰。训练场的地图可以看作一棵以 1 为根节点的树，训练场的终点为这棵树的叶子结点，树上的每个结点最多有一只怪兽，结点与结点间的边上没有怪兽。每一个有怪兽的结点上牛牛都需要打倒怪兽才算安全，并且牛 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Zhenghao-Liu
发表于 2020-07-31 21:16:27
因为边的问题，单看边是无法得到哪个是父哪个是子的所以当成无向图来存取边，即邻接表然后从根节点即1，开始dfs，即可 那么怎样保证不会重复dfs到父节点呢，可以用use数组将当前路径上遍历过的节点做标记 怎么判断叶子节点：上述用了use数组，那么当一个节点与他相邻的所有边的节点都已经被标记过了，即已 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 哆啦B梦2112
发表于 2021-09-07 09:31:09
题意 给定一颗树，每个节点有一个0/1的值。求有多少个叶节点满足根节点到叶节点的路径上的点的值之和不大于2. 思考 因为每个节点的值是非负的(所以走必须经过路径外的点并不会使答案更优)。所以从根节点到叶节点的最小路径是确定的，就是一直向下的那条路径。 方法一( 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 简单666
发表于 2021-09-07 15:10:21
题意： 给你一棵个节点的有根树，根节点为1，每个节点的权值为0或者1，问有多少条从根节点到叶子节点的路径，使得所经过的节点权值和不超过2 ？ 解法一（深度优先搜索） 从根节点对整棵树进行dfs，然后计算答案 具体的：     我们定义递归函数表示当前 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-09-12 15:38:21
思路： 题目的主要信息： 一棵以1为根节点的树，节点值为0或者1 最多经过两个值为1的节点的情况下，求有多少条从根达到叶结点的路径 方法一：dfs具体做法：我们首先根据题目给出的边信息构建邻接矩阵，可以访问某个节点的所有相邻节点。然后从根节点开始dfs递归，递归过程不断更新路径中1的数量coun 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”