在线午夜精品自拍小视频_无码av无码专区线_亚洲无码精品人妻_人人澡欧美一区

劍指offer之樹的子結構

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 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寫錯了，實現(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é)點也會進行比較


 

作者：chen.yu
深信服三年半工作經驗，目前就職游戲廠商，希望能和大家交流和學習,
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎入門進階人工智能(鏈接)