1 題目

輸入兩顆二叉樹A和B，判斷B是不是A的子結構（B樹是A樹的子結構）
比如：
? ? ? ? ? ? ? ? ? 2
? ? 樹A ? ?3 ? ?5 ? ? ?樹B ? 5
? ? ? ? ? ? 1 ?4 ?2 ?3? ? ? ? ?2 ? 3
很明顯樹B是樹A的子結構

?

?

?

?

?

?

2 代碼實現(xiàn)

#include <stdio.h>#define true 1 #define false 0typedef 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寫錯了，實現(xiàn)如下

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節(jié)點和樹A的5節(jié)點進行匹配，然后樹B的2節(jié)點和樹A的2節(jié)點進行匹配，接下來，樹A的left是NULL了，直接返回false,那么后面的 ?&& is_same(head1->right, head2->right)
就不會再執(zhí)行了，所以返回false,然而B數(shù)的右結構沒有進行比較是直接false了，所以我們需要把

if (head2 == NULL) {return true; }

寫在前面，確保比較B樹的右節(jié)點也會進行比較

總結

以上是生活随笔為你收集整理的剑指offer之树的子结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。