劍指offer之樹的子結構

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

           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樹的右節點也會進行比較