程序员代码面试指南 3.11：判断是否包含全部的拓扑结构

1、思路

• 若树root1中某棵子树节点的值与树root2头节点的值一样，则从这两个头节点开始匹配，匹配的每一步都让root1上的节点跟着root2上的节点的先序遍历移动，每移动一步都检查两棵树当前节点的值是否相同；

• 因为root1的每棵子树上都可能匹配出root2，所以都要检查一边，故时间复杂度为 ，其中 和 分别为root1与root2的节点个数。

2、代码

#include <iostream>

using namespace std;

struct TreeNode                             //二叉树节点
{
    int val;
    TreeNode *left, *right;

    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
};

void createTree(TreeNode* root, int &n)     //建树
{
    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;

    root->val = rootVal;

    if (leftVal != 0)
    {
        root->left = new TreeNode(leftVal);
        createTree(root->left, -- n);
    }

    if (rightVal != 0)
    {
        root->right = new TreeNode(rightVal);
        createTree(root->right, -- n);
    }
}

bool check(TreeNode* root1, TreeNode* root2)
{
    if (root2 == nullptr) return true;
    if (root1 == nullptr || root1->val != root2->val) return false;

    //按先序遍历的顺序同时遍历两课二叉树
    return check(root1->left, root2->left) && check(root1->right, root2->right);
}

//判断 root1 是否包含 root2
bool contains(TreeNode* root1, TreeNode* root2)
{
    if (root2 == nullptr) return true;
    if (root1 == nullptr) return false;

    return check(root1, root2) || contains(root1->left, root2) || contains(root1->right, root2);
}

int main()
{
    int n, rootVal;

    cin >> n >> rootVal;
    TreeNode *root1 = new TreeNode(rootVal);
    createTree(root1, n);

    cin >> n >> rootVal;
    TreeNode *root2 = new TreeNode(rootVal);
    createTree(root2, n);

    if (contains(root1, root2))
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }

    return 0;
}