题目

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

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

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

输入描述:
第一行两个正整数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

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
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;
}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/122311476