1 题目
输入两颗二叉树A和B，判断B是不是A的子结构（B树是A树的子结构）
比如：
2
树A 3 5 树B 5
1 4 2 3 2 3
很明显树B是树A的子结构
2 代码实现
#include <stdio.h> #define true 1 #define false 0 typedef struct Node { int value; struct Node* left; struct Node* right; } Node; int has_sub_tree(Node *head1, Node *head2) { int result = false; if (head1 != NULL && head2 != NULL) { printf("head1->value is %d\n", head1->value); printf("head2->value is %d\n", head2->value); if (head1->value == head2->value) { result = is_same(head1, head2); } if (!result) { result = has_sub_tree(head1->left, head2); } if (!result) { result = has_sub_tree(head1->right, head2); } } return result; } int is_same(Node *head1, Node *head2) { if (head2 == NULL) { return true; } if (head1 == NULL) { return false; } printf("is_same head1->value is %d\n", head1->value); printf("is_same head2->value is %d\n", head2->value); if (head1->value != head2->value) { return false; } return is_same(head1->left, head2->left) && is_same(head1->right, head2->right); } void printf_tree(Node *head) { if (head != NULL) { printf("val is: %d\n", head->value); printf_tree(head->left); printf_tree(head->right); } } int main() { /* 2 * 3 5 5 * 1 4 2 3 2 3 * */ Node head1, node1, node2, node3, node4, node5, node6; Node head2, node7, node8; head1.value = 2; node1.value = 3; node2.value = 5; node3.value = 1; node4.value = 4; node5.value = 2; node6.value = 3; head1.left = &node1; head1.right = &node2; node1.left = &node3; node1.right = &node4; node2.left = &node5; node2.right = &node6; node3.left = NULL; node3.right = NULL; node4.left = NULL; node4.right = NULL; node5.left = NULL; node5.right = NULL; node6.left = NULL; node6.right = NULL; head2.value = 5; node7.value = 2; node8.value = 3; head2.left = &node7; head2.right = &node8; node7.left = NULL; node7.right = NULL; node8.left = NULL; node8.right = NULL; printf_tree(&head1); printf_tree(&head2); int result = has_sub_tree(&head1, &head2); printf("result is %d\n", result); return 0; }
3 运行结果
val is: 2 val is: 3 val is: 1 val is: 4 val is: 5 val is: 2 val is: 3 val is: 5 val is: 2 val is: 3 head1->value is 2 head2->value is 5 head1->value is 3 head2->value is 5 head1->value is 1 head2->value is 5 head1->value is 4 head2->value is 5 head1->value is 5 head2->value is 5 is_same head1->value is 5 is_same head2->value is 5 is_same head1->value is 2 is_same head2->value is 2 is_same head1->value is 3 is_same head2->value is 3 result is 1
4 总结
一开始is_same写错了，实现如下
int is_same(Node *head1, Node *head2) { if (head1 == NULL) { return false; } if (head2 == NULL) { return true; } printf("is_same head1->value is %d\n", head1->value); printf("is_same head2->value is %d\n", head2->value); if (head1->value != head2->value) { return false; } return is_same(head1->left, head2->left) && is_same(head1->right, head2->right); }
这样写导致的错误就是，比如
2
树A 3 5 树B 5
1 4 2 3 2 3
树B的5节点和树A的5节点进行匹配，然后树B的2节点和树A的2节点进行匹配，接下来，树A的left是NULL了，直接返回false,那么后面的 && is_same(head1->right, head2->right)
就不会再执行了，所以返回false,然而B数的右结构没有进行比较是直接false了，所以我们需要把
if (head2 == NULL) { return true; }
写在前面，确保比较B树的右节点也会进行比较
