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