判断树A是否为另一树B的子结构

题目的意思：

Paste_Image.png

首先直观的想到，我们先在A中找到B的根节点，然后递归的检查B所有的节点是否在A中相同的位置：

//check if t1 has t2
//在这个函数里面，我们有很多出口，不满足条件的直接return false出去，这样写简单
bool partOfTree(treeNode* t1, treeNode* t2)
{
    if (!t1)
        return false;
    if (!t2)
        return true;//only branch that returns true

    if (t1->data != t2->data)
        return false;
    
    return  partOfTree(t1->lNode, t2->lNode)&&partOfTree(t1->rNode, t2->rNode);
//这个return写的好

}

这个函数就是检查，当在A中找到B的根节点之后做的事情。我只需要返回是否相等就行。

然后就是，在A中找B的根节点然后调用上面的函数判断：
注意事项见注释，我有一个误区就是如果在A找到了根节点然后判断不相等就直接退出，但是A中可能有多个和B根节点值相同的节点啊，所以这个不满足后面接着判断。
除非题目说明是特殊的每个元素只出现一次的树。

bool hasSubTreeCore(treeNode* t1, treeNode* t2)//find the root node of tree2 in tree1
{
    bool result = false;

    if (t1->data == t2->data)
        result= partOfTree(t1, t2);
    //注意这里不要直接返回!   因为当前的这个节点不符合，可能下面还有相同值的节点！

    if (!result&&t1->lNode)
        result = hasSubTreeCore(t1->lNode, t2);
    if (!result&&t1->rNode)
        result = hasSubTreeCore(t1->rNode, t2);

    return result;//统一的函数出口
}

最后完整的函数还有一个驱动程序，这个函数主要是排除一些非法的输入

bool hasSubTreeCore(treeNode*,treeNode*);
bool hasSubTree(treeNode* t1, treeNode* t2)//这个函数在于排除掉一些不符合要求的输入。
{
    if (!t1&&!t2)
        return true;
    if (!t1&&t2 || !t2&&t1)
        return false;

    return hasSubTreeCore(t1,t2);
}

另外，如果题目给定的树是一个二元查找树的话，也就是查找根节点方便一点，然后判断只需要判断一次，其他的应该都一样吧。

欢迎讨论!

文章参考何海涛大神文章