剑指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
    树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树的右节点也会进行比较


 

作者：chen.yu
深信服三年半工作经验，目前就职游戏厂商，希望能和大家交流和学习,
微信公众号：编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)