4-08:判断子树

问题:判断子树

给定两颗二叉树A,B,判断A是否是B的子结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool issubtree(TreeNode* bigtree, TreeNode* smalltree)
{
    if (smalltree == NULL)
        return true;
    if (bigtree == NULL)
        return false;
    if (bigtree->getvalue() == smalltree->getvalue())
        return issubtree(bigtree->getleft(), smalltree->getleft()) && issubtree(bigtree->getright(), smalltree->getright());
    else
        return false;
}
 
bool findsubtree(TreeNode* bigtree,TreeNode* smalltree)
{
    if (bigtree == NULL || smalltree == NULL)
        return false;
    bool result = false;
    if (bigtree->getvalue() == smalltree->getvalue())
        result = issubtree(bigtree, smalltree);
    if (!result)
        result = findsubtree(bigtree->getleft(), smalltree);
    if (!result)
        result = findsubtree(bigtree->getright(), smalltree);
    return result;
}
Category technology