剑指offer - 树的子结构

题目

输入两棵二叉树A和B，判断B是不是A的子结构。二叉树节点的定义如下：

struct BinaryTreeNode {
    double m_dbValue;
    BinaryTreeNode *m_pLeft;
    BinaryTreeNode *m_pRight;
};

下图中的二棵二叉树，由于A中有一部分子树的结构和B是一样的，因此，B是A的子结构

1.png

思路

要查找树A是否存在和树B结构一样的子树，可以分为两步：

1、在树A中找到和树B根结点的值一样的结点R
2、判断树A中以R为根结点的子树是不是包含和树B一样的结构

以上面的两棵树来分析

首先试着在树A中找到值为8（树B根结点的值）的结点，从树A的根结点开始遍历，我们发现它的根结点的值就是8。

接着判断树A下面的子树是不是含有和树B一样的结构，如下图，在树A，根结点的左子结点的值是8，而树B的根结点的左子结点是9，对应的两个结点不同

download.png

因此，我们仍然需要遍历树A，接着查找值为8的结点。在树的第二层中找到了一个值为8的结点，然后进行第二步判断，即判断这个结点下面的子树是否含有和树B一样的结构。

于是我们遍历这个结点下面的子树，先后得到两个子结点9和2，这和树B的结构完成 相同。此时我们在树A中找到了一棵和树B的结构一样的子树，因此树B是树A的子结构

算法实现

#include <iostream>
using namespace std;

struct BinaryTreeNode {
    double m_dbValue;
    BinaryTreeNode *m_pLeft;
    BinaryTreeNode *m_pRight;
};

bool Equal(double num1, double num2);
bool DoesTree1HaveTree2(BinaryTreeNode *pRoot1, BinaryTreeNode *pRoot2);

bool HasSubtree(BinaryTreeNode * pRoot1, BinaryTreeNode *pRoot2) {
    bool result = false;

    if (pRoot1 != nullptr && pRoot2 != nullptr) {

         // 根结点一样
        if (Equal(pRoot1->m_dbValue, pRoot2->m_dbValue))
            result = DoesTree1HaveTree2(pRoot1, pRoot2);

        if (!result) // 子树是否在左子树
            result = HasSubtree(pRoot1->m_pLeft, pRoot2);

        if (!result) // 子树是否在右子树
            result = HasSubtree(pRoot1->m_pRight, pRoot2);
    }

    return  result;
}

// 树1是否包含树2
bool DoesTree1HaveTree2(BinaryTreeNode *pRoot1, BinaryTreeNode *pRoot2) {
    if (pRoot2 == nullptr)
        return true;

    if (pRoot1 == nullptr)
        return false;

    if (!Equal(pRoot1->m_dbValue, pRoot2->m_dbValue))
        return true;

    return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft) &&
    DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);
}

// 判断值相等
bool Equal(double num1, double num2) {
    if ((num1 - num2 > - 0.0000001) && (num1 - num2) < 0.0000001)
        return true;
    else
        return false;
}

注意：由于计算机表示小数（包括float和double型小数）都有误差，我们不能直接用等号（==）判断两个小数是否相等。如果两个小数的差的绝对值很小，如小于0.0000001，就可以认为它们相等。

参考

《剑指offer》