题目
有一棵二叉树，树上的叶子节点定义为“樱桃”。现在需要找出树上有多少个满足如下子结构的“樱桃”串，即一串上刚好有两颗“樱桃”。
比如如下的一棵树，红框标示的有两个符合要求的结构，答案就是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
输出样例：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; }
