首页 > 试题广场 >

树上摘樱桃

[编程题]树上摘樱桃
  • 热度指数：1707 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有一棵二叉树，树上的叶子节点定义为“樱桃”。现在需要找出树上有多少个满足如下子结构的“樱桃”串，即一串上刚好有两颗“樱桃”。

比如如下的一棵树，红框标示的有两个符合要求的结构，答案就是2



又比如下面的这颗树，没有任何符合要求的子结构，则答案是0



输入描述:
第一行两个正整数m, n，空格分开，分别代表总共有树上有多少个节点，和树上有多少条边，2<=m<=100,  1<=n<=100
下面有n行，每行为3个部分，用空格分割，第一个数字为某非叶子节点的id, 第二个为该边为left还是right，第三个为子节点的id
注意：节点id彼此不会重复，id 1为根节点 


输出描述:
一个整数，标示符合要求的子结构的数量
示例1

输入

10 9
1 left 2
1 right 3
2 left 4
2 right 5
3 right 6
6 left 7
6 right 8
8 left 9
8 right 10

输出

2

说明

如题目说明的第一个样例图，可以看到，2-4-5子串，8-9-10子串，两个子串符合条件，所以答案为2
算法知识视频讲解
添加回答
JavaScript
牛客93930297号头像 牛客93930297号
let mn = readline().split(' ')
let m = mn[0],n = mn[1]
let line
let arr = []
let j = 0
while(line = readline()) {
    arr[j++] = line.trim().split(' ')//变成一个二维数据
}
let count = 0
let map = new Map()
for(let i = 0;i<arr.length;i++) {
    let j = 0
    map.has(arr[i][j]) ? map.set(arr[i][j],map.get(arr[i][j])+1):map.set(arr[i][j],1)
}
let x = 0
for(let i = 0;i<arr.length -1;i++) {
    let j  = 2
    if(!map.has(arr[i][j]) && !map.has(arr[i+1][j]) && (arr[i][0] == arr[i+1][0])) {
        count++
    }
}
console.log(count)
发表于 2021-07-08 21:52:16 回复(3)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 前端工程师 算法工程师 网易 安全工程师 2021 Java工程师
上传者：小小
难度：
1条回答 5108浏览

热门推荐

通过挑战的用户

相关试题

树上摘樱桃

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号