【剑指Offer】树的子结构

题目： 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

解法：

（1）树的遍历

递归的到母树上面匹配子树的结构，存在即true，否则是false。 第1步：比较根节点，如果根节点的值不相同，则必然是false。 第2步：去遍历左子树和右子树 注意：边界条件，如果子树为空的时候递归结束。 同时要注意检验非法输入：pRoot1 = NULL Code:

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { bool res = false; if(pRoot1 == NULL || pRoot2 == NULL) { return false; } if(pRoot1->val == pRoot2->val){ res = DoesT1HasT2(pRoot1,pRoot2); //以这个根节点为为起点判断是否包含Tree2 } //如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree2 if(!res) res = HasSubtree(pRoot1->left,pRoot2); //如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2 if(!res) res = HasSubtree(pRoot1->right,pRoot2); return res; } bool DoesT1HasT2(TreeNode* t1, TreeNode* t2){ if(t2 == NULL) return true; //如果Tree2已经遍历完了都能对应的上，返回true if(t1 == NULL) return false; //如果Tree2还没有遍历完，Tree1却遍历完了。返回false if(t1->val != t2->val) return false; //如果其中有一个点没有对应上，返回false //如果根节点对应的上，那么就分别去子节点里面匹配 return DoesT1HasT2(t1->left, t2->left) && DoesT1HasT2(t1->right, t2->right); } };

（2）方法2：

踩坑：我原本想的是将两棵树进行序列化，之后利用kmp算法在母树S的序列中去找子树T的序列，如果找到返回index，否则返回-1

一定要注意：方法2在此题的情况下并不正确，注意一定要区分以下2个概念：

（1）树的子结构

（2）给定的二叉树T是否是母树S的子树

这个题在剑指offer上是这么描述的：

在这里[8,9,2]就是母树S的一个子结构，但绝对不是一棵子树，因为子树一旦确定了根节点的时候就整棵树都得拿到（可以看一下leetcode572题，很严谨）

但是牛客的后台数据应该是不够强大，我看到了讨论区有一份这样的代码，本来是不可以通过的，但是却AC了~

（没图还说个锤子，来，上图！）

你看它居然真的通过了

分析一波： 这份代码将两棵树序列化，之后比较字符串，重点是他没有做任何的结束边界处理，比如遇到空指针的时候等等。。。。。

还是上图推翻他的代码可行性

反例：

这样的子树T根本就不是母树S的子结构 但是看他代码的样例结果肯定会返回true，然而这是个错误的结果。。。。。 思考是一件幸福的事情，，加油！