Description网易2021校招笔试-算法工程师（正式第一批） 有一棵二叉树，树上的叶子节点定义为“樱桃”。现在需要找出树上有多少个满足如下子结构的“樱桃”串，即一串上刚好有两颗“樱桃”。 简单说，就是某个节点的左右孩子都是叶子节点，即为一个串。 比如如下的一棵树，红框标示的有两个符合要求的结构，答案就是2输入格式第一行两个正整数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
这道题看着挺好理解的，就是找左右孩子都是叶子结点的结点呗，那么它的判断条件就是if(它有左孩子 && 它有右孩子 && 它的左孩子没有左孩子 && 它的左孩子没有右孩子 && 它的右孩子没有左孩子 && 它的右孩子没有右孩子)，满足这个条件，计数器+1。
好了，我们现在知道要找的结点应满足什么条件了，那我们该怎么判断这六个条件是否满足呢？从老师那里发现了一个很巧妙的方法，用二维数组存储结点，t[n][2]={0}，全部初始化为0，即n行2列的二维数组，第一列存放左孩子，第二列存放右孩子。当x=1时，若L=t[x][0]==0，说明结点1没有左孩子，若L=t[x][0]!=0，说明结点1有左孩子；若t[L][0]==0，说明结点1的左孩子没有左孩子，若t[L][1]!=0，说明结点1的左孩子有左孩子。这个能明白叭？不明白的话照着上面给的样例和下面的代码段画一画~
现在原理都知道的差不多了吧~接下来就要看递归的了~
就拿样例来说说吧~
第一次在主函数中调用函数dfs(1),从结点1开始深搜。那么我们知道结点1的左孩子是2，右孩子是3。首先搜索dfs(2)，那么2的左孩子是4，右孩子是5，再搜索dfs(4)，然后4没有左右孩子，满足递归调用的结束条件，返回，搜索dfs(5)，结点5也没有左右孩子，返回，搜索dfs(3)，3没有左孩子，只有右孩子6……所以最后一次递归调用得到结点8有左右孩子，且它的左右孩子都没有左右孩子，那么计数器ans++。
每当p==0的时候，说明该结点没有左右孩子，那么它必然不是我们所要找的“樱桃”，所以直接结束递归调用，返回上一层。每当深搜dfs( )时，就会进行一次if判断，如果不满足，就继续返回到上一层，直到回到结点1的左孩子。
void dfs(int p)
{
if(p==0)
return;
int lchild,rchild;
lchild=t[p][0];
rchild=t[p][1];
dfs(lchild);
dfs(rchild);
if(lchild && rchild && !t[lchild][0] && !t[lchild][1] && !t[rchild][0] && !t[rchild][1])
ans++;
}
全部代码
#includeusing namespace std; int t[105][2]={0},n,m,ans=0; void dfs(int p) { if(p==0) return; int lchild,rchild; lchild=t[p][0]; rchild=t[p][1]; dfs(lchild); dfs(rchild); if(lchild && rchild && !t[lchild][0] && !t[lchild][1] && !t[rchild][0] && !t[rchild][1]) ans++; } int main() { int i,x,y; string s; cin>>m>>n; for(i=1; i<=n; i++) { cin>>x>>s>>y; //[x][0]存x的左子树，[x][1]存x的右子树 if(s=="left") t[x][0]=y; else t[x][1]=y; } dfs(1); cout<
