【网易算法笔试】树上摘樱桃

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

题目

有一棵二叉树,树上的叶子节点定义为“樱桃”。现在需要找出树上有多少个满足如下子结构的“樱桃”串,即一串上刚好有两颗“樱桃”。

image.png

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

image.png

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

image.png

输入描述:

第一行两个正整数m, n,空格分开,分别代表总共有树上有多少个节点,和树上有多少条边,2<=m<=100, 1<=n<=100。下面有n行,每行为3个部分,用空格分割,第一个数字为某非叶子节点的id, 第二个为该边为left还是right,第三个为子节点的id。

注意:节点id彼此不会重复,id 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


思路

(1)首先建树,注意该题的输入输出格式,需要根据左边还是右边,确定将child被当前节点id的左指针,还是右指针指向。


(2)符合要求的樱桃串(题目中的框框内)的判断,应该是!root->left->left && !root->left->right && !root->right->left && !root->right->right,该节点的“后代”中只有左孩子和右孩子这两个节点了。


代码

#include<iostream>
#include<vector>
#include<string>
using namespace std;
// 定义节点类
class Node{
public:
    Node *left = NULL;
    Node *right = NULL;
};
int Numfun(Node* root){
    if(!root) return 0;
    if(!root->left) return Numfun(root->right);
    if(!root->right) return Numfun(root->left);
    //关键判断
    if(!root->left->left && !root->left->right 
      && !root->right->left && !root->right->right) return 1;
    return Numfun(root->left) + Numfun(root->right);
}
int main(){
    int m, n;
    cin >> m >> n;
    //用vector里的index表示id,因为id从1开始,所以size为m+1
    vector<Node*> a(m+1);
    for(int i = 1; i < m+1; i++){
        a[i] = new Node();
    }
    for(int i = 0; i < n; i++){
        int id;
        cin >> id;
        string position;
        cin >> position;
        int child;
        cin >> child;
        if(position[0] == 'l'){
            a[id]->left = a[child];
        }
        else{
            a[id]->right = a[child];
        }
    }
    cout << Numfun(a[1]);
    return 0;
}
相关文章
|
消息中间件 Java 调度
自顶向下学习 RocketMQ(六):定时消息
定时消息会暂存在名为 SCHEDULE_TOPIC_XXXX 的 topic 中,并根据 delayTimeLevel 存入特定的 queue,queueId = delayTimeLevel – 1,即一个 queue 只存相同延迟的消息,保证具有相同发送延迟的消息能够顺序消费。broker 会调度地消费 SCHEDULE_TOPIC_XXXX,将消息写入真实的 topic。
自顶向下学习 RocketMQ(六):定时消息
|
数据采集 自然语言处理 搜索推荐
图文详解 DFS 和 BFS | 算法必看系列知识二十四
深度优先遍历(Depth First Search, 简称 DFS) 与广度优先遍历(Breath First Search)是图论中两种非常重要的算法,生产上广泛用于拓扑排序,寻路(走迷宫),搜索引擎,爬虫等,也频繁出现在高频面试题中。
35668 6
图文详解 DFS 和 BFS | 算法必看系列知识二十四
|
存储 Java 数据库
Spring Boot与分布式事务的最佳实践
Spring Boot与分布式事务的最佳实践
【面试问题】final 和可以保证可见性吗?
【1月更文挑战第27天】【面试问题】final 和可以保证可见性吗?
|
搜索推荐 Android开发
eclipse IDEA中字母大小写转换快捷键
eclipse IDEA中字母大小写转换快捷键
445 0
|
设计模式 监控 安全
【Hystrix技术指南】(1)基本使用和配置说明
【Hystrix技术指南】(1)基本使用和配置说明
435 0
|
缓存 Java Maven
maven出现Dependency not found 和Could not find artifact的解决方法(已解决)
maven出现Dependency not found 和Could not find artifact的解决方法(已解决)
5721 0
|
敏捷开发 测试技术 数据库
PowerMock(一):PowerMock的基本使用
您好,我是码农飞哥,感谢您阅读本文!本文主要介绍PowerMock的基本使用。
1788 0
|
网络协议 NoSQL Java
SpringBoot 整合 mongoDB 并配置连接池
SpringBoot整合mongoDB并配置连接池
5789 0
|
域名解析 Oracle 关系型数据库
三步解决 Maven 无法下载依赖包的问题
本文主要为大家讲解 Maven 的依赖包下载问题。
7152 0
三步解决 Maven 无法下载依赖包的问题