本文共 4297 字，大约阅读时间需要 14 分钟。
原文链接：http://ac.jobdu.com/problem.php?pid=1520
题目1520：树的子结构
输入两颗二叉树A，B，判断B是不是A的子结构。
输入可能包含多个测试样例，输入以EOF结束。
对于每个测试案例，输入的第一行一个整数n,m(1<=n<=1000,1<=m<=1000)：n代表将要输入的二叉树A的节点个数（节点从1开始计数），m代表将要输入的二叉树B的节点个数（节点从1开始计数）。接下来一行有n个数，每个数代表A树中第i个元素的数值，接下来有n行，第一个数Ki代表第i个节点的子孩子个数，接下来有Ki个树，代表节点i子孩子节点标号。接下来m+1行，与树A描述相同。
对应每个测试案例，
若B是A的子树输出”YES”(不包含引号)。否则，输出“NO”（不包含引号）。
7 38 8 7 9 2 4 72 2 32 4 5002 6 7008 9 22 2 3001 12030
YESNO
B为空树时不是任何树的子树。
1、在tree中找到（先序遍历）与子树（root2）有相同根节点的节点root1
2、同时对root1和root2做先序遍历，比较两棵树的左右子树是否相同
注意：本题测试用例有点坑
上网查找：
首先题目要求n与m的范围不能为0，但是测试用例中第三个和第四个有可能分别是第一个树空和第二个数空的特殊情况。因此，要特别注意这里，在scanf("%d %d",&n,&m)的时候对mn注意限制的范围。
另外用例并没有给出单个叶子的情况，这时注意，当输入为1时，只有一个节点，并且是左子树节点。
例如当只有一个孩子时输入的是：
1 左孩子节点索引
本题根据上面提示修改后第三个测试用例还是未能通过。。。
代码如下：
#include#include #include using namespace std;struct treeNode { int data; treeNode *left; treeNode *right;}; bool findSubTree(treeNode *root1, treeNode *root2){ if(root2 == NULL) return true; if(root1 == NULL) return false; if(root1->data == root2->data) return findSubTree(root1->left, root2->left) && findSubTree(root1->right, root2->right); return false;} bool hasSubTree(treeNode *root1, treeNode *root2) { bool result = false; if(root1 != NULL && root2 != NULL) { if(root1->data == root2->data) result = findSubTree(root1, root2); if(!result) result = hasSubTree(root1->left, root2); if(!result) result = hasSubTree(root1->right, root2); } return result;}//tree[i][0]节点值//tree[i][1]节点左孩子序号//tree[i][2]节点右孩子序号treeNode *create(int tree[1000][3]){ treeNode *root = (treeNode *)malloc(sizeof(treeNode)); root->data = 0; root->left = NULL; root->right = NULL; queue q; while(!q.empty()) q.pop(); q.push(root); int i = 0; while(!q.empty()) { treeNode *root = q.front(); q.pop(); root->data = tree[i][0]; if(tree[i][1] != 0){ root->left = (treeNode *)malloc(sizeof(treeNode)); q.push(root->left); } else root->left = NULL; if(tree[i][2] != 0){ root->right = (treeNode *)malloc(sizeof(treeNode)); q.push(root->right); } else root->right = NULL; if(tree[i][1] == 0 && tree[i][2] == 0) { root->left = NULL; root->right = NULL; } i ++; } return root;}int main() { int n, m; int tree[1000][3]; int subTree[1000][3]; while(scanf("%d %d", &n, &m) != EOF) { if(m == 0 || n == 0){ printf("NO\n"); continue; } for(int i = 0; i < n; i ++) scanf("%d", &tree[i][0]); for(int i = 0; i < n; i ++) { int x; int l; int r; scanf("%d", &x); if(x == 0) { tree[i][1] = 0; tree[i][2] = 0; continue; } else if(x == 1){ scanf("%d", &l); tree[i][1] = l; tree[i][2] = 0; } else{ scanf("%d %d", &l, &r); tree[i][1] = l; tree[i][2] = r; } } for(int i = 0; i < m; i ++) scanf("%d", &subTree[i][0]); for(int i = 0; i < m; i ++) { int x; int l; int r; scanf("%d", &x); if(x == 0) { subTree[i][1] = 0; subTree[i][2] = 0; continue; } else if(x == 1){ scanf("%d", &l); subTree[i][1] = l; subTree[i][2] = 0; } else{ scanf("%d %d", &l, &r); subTree[i][1] = l; subTree[i][2] = r; } } treeNode *root = create(tree); treeNode *subRoot = create(subTree); bool result = hasSubTree(root, subRoot); if(result) printf("YES\n"); else printf("NO\n"); } return 0;}/************************************************************** Problem: 1520 Language: C++ Result: Wrong Answer****************************************************************/
转载地址：http://yesob.baihongyu.com/