给你两颗二叉树,请编写一个函数检验这两颗树是否相等。 如果两颗树在结构上相同,并且节点具有相同的值,则认为它们是相同的。如下所示 不同的例子如下所示: 输入 第一行为两颗树的长度n和m(1≤n,m≤50);第二行为第一颗树的数组形式;第三行为第二棵树的数组形式。 当tree[i] = 0时,表示为空结点。 输出 如果两颗树相同请输出“YES”,否则输出“NO” 样例输入 Copy 3 5 1 2 3 1 2 3 0 0 样例输出 Copy YES用c语言怎么写
时间: 2024-02-21 12:57:30 浏览: 4
以下是用 C 语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int compareTrees(TreeNode* p, TreeNode* q) {
if (p == NULL && q == NULL) {
return 1;
} else if (p == NULL || q == NULL) {
return 0;
} else if (p->val != q->val) {
return 0;
} else {
return compareTrees(p->left, q->left) && compareTrees(p->right, q->right);
}
}
TreeNode* createTree(int* arr, int n, int i) {
if (i >= n || arr[i] == 0) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = arr[i];
root->left = createTree(arr, n, 2 * i + 1);
root->right = createTree(arr, n, 2 * i + 2);
return root;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
int* arr1 = (int*)malloc(sizeof(int) * n);
int* arr2 = (int*)malloc(sizeof(int) * m);
for (int i = 0; i < n; i++) {
scanf("%d", &arr1[i]);
}
for (int i = 0; i < m; i++) {
scanf("%d", &arr2[i]);
}
TreeNode* root1 = createTree(arr1, n, 0);
TreeNode* root2 = createTree(arr2, m, 0);
if (compareTrees(root1, root2)) {
printf("YES");
} else {
printf("NO");
}
free(arr1);
free(arr2);
return 0;
}
```
思路:我们可以使用递归的方式来判断两颗二叉树是否相等。首先比较根节点的值是否相等,如果相等,则继续递归地比较左子树和右子树是否相等。如果都相等则返回1,否则返回0。递归的基本情况是当两个节点都为空时返回1,当其中一个节点为空时返回0。然后我们可以用 createTree 函数来根据输入的数组构建二叉树,最后我们只需要比较两个根节点是否相等即可。