子节点计数
Time Limit: 1000MS Memory limit: 65536K
题目描述
给定一棵树的前序和中序序列,求以指定关键字节点为根的子树的节点个数。
输入
第一行包含一个整数 T(T <= 20),表示有 T 组测试数据;
每组测试数据第一行为整数 N(1 <= N <= 50),表示树的总结点数;接下来两行为前序和中序序列;第三行有正整数 M( 1 <= M <= 30),表示有 M 条查询; 最后 M 行有M 个整数,表示查询以该整数为关键字的节点。
输入保证前序和中序序列合法且任意两个节点关键字不同。
输出
每组测试数据有 M 行,每行有一个整数表示每条查询的节点总数。
示例输入
1 5 23 2 67 59 98 2 23 59 67 98 4 23 2 67 59
示例输出
5 1 3 1
这是前几天选拔赛的一个题，当时就是这个思路，但是调试结果不对，不知道哪里手误了。。今天又这样写了一遍，AC果断姗姗来迟了。。
#include <stdio.h> #include <stdlib.h> struct node {struct node *left, *right;int data; }; void build(struct node* &p, int len, int s1[], int s2[]) {if(len <= 0)return;p = (struct node*)malloc(sizeof(struct node));p->data = s1[0];p->left = p->right = NULL;int m = 0;while(s1[0] != s2[m])m++;build(p->left, m, s1+1, s2);build(p->right, len-m-1, s1+m+1, s2+m+1); } int sum; void preorder(struct node* &root) {if(root == NULL)return;sum++;preorder(root->left);preorder(root->right); } void search(int key, struct node* &p) {if(p == NULL)return;if(p->data == key){preorder(p);return;}else{search(key, p->left);search(key, p->right);} } int main() {int t, n, m, x, a[60], b[60];scanf("%d", &t);while(t--){scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%d", &a[i]);for(int i = 0; i < n; i++)scanf("%d", &b[i]);struct node *root;build(root, n, a, b);scanf("%d", &m);while(m--){scanf("%d", &x);sum = 0;search(x, root);printf("%d\n", sum);}}return 0; }
