题目描述
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
暴力解法
从s的根节点开始遍历，查看该节点下的子树是否与t相同。方法是同步对s和t进行遍历，一旦出现s和t有不同（包括只有其中一个为NULL，或都不为NULL时value不同），就返回为false。如果最终返回给调用比较函数的地方是false，那么就继续为s的下一个节点重新遍历。
class Solution {
public:
bool isSameTree(TreeNode * sNow, TreeNode * tNow)
{
if(!sNow && !tNow) return true;
if((!sNow && tNow) || (sNow && !tNow) || (sNow->val != tNow->val))
return false;
//这里直接返回的是：当左子树和右子树全部相等时，就是匹配的。
//为什么没有比较本节点？因为假如本节点value不一样，就已经在上面一个if被返回false了，不会执行到最后的return
return isSameTree(sNow->left, tNow->left) && isSameTree(sNow->right, tNow->right);
}
bool dfs(TreeNode * sNow, TreeNode * tNow)
{
if(!sNow) return false;
//由于||和&&的短路特性，||后面的表达式只有前面为false才会被运行
return isSameTree(sNow, tNow) || dfs(sNow->left, tNow) || dfs(sNow->right, tNow);
}
bool isSubtree(TreeNode* s, TreeNode* t) {
bool isSub = dfs(s, t);
return isSub;
}
};
显然暴力解法的复杂度太高了。其时间复杂度为O(|s|*|t|)，其中|s|和|t|是s树和t树的节点数量。空间复杂度方面，递归栈最大为O(max{ds, dt})，其中ds, dt分别是s和t的最大深度。
遍历后匹配字符串
为了解决暴力解法复杂度高的问题，一个容易想到的思路是首先对s和t前序遍历之后形成数组（字符串），然后再来进行字符串的匹配。
这样会出现一个显而易见的问题，当t是s的“一部分”而并非子树时，也就是t的“底端”比s多一些节点时，会出现匹配失误的情况。为了解决该问题，可以将叶节点左、右节点的NULL也插入到字符串中，这样可以保证匹配唯一。
遍历过后，就成为了一个字符串匹配问题。我们把较长的需要寻找子串的一个叫做文本串S（此处是s树得来的），匹配的目标叫做模式串P（此处是t树得来的）。
直接匹配
进行字符串匹配时，首先可以从暴力匹配想起。其思路是：对于S[i], P[j]，如果匹配，则继续往后一位匹配。如果失配，则S退回到i = i-j+1，也就是与j开始匹配的后一位，P退回到j = 0，重新开始匹配过程。
此算法的浪费之处在于，假如失配时S[i-j+1]与S[i-j]并不相同，那么P重新从S[i-j+1]开始匹配时必然是失配的，在找到下一个匹配开始点前的操作都是重复的。
KMP算法匹配
KMP算法原理
KMP算法的核心在于利用了已经匹配过的信息。其关键在于加入了一个next数组。
next数组的意义是：next[k]表示从模式串的子串P[0]到P[k]中，相同前缀后缀的最大长度。例如：P = ABCDFABGF，那么next[6] = 2，即子串ABCDFAB的相同前缀后缀最长是AB，长度为2。
有了next数组，如果首位失配则S[i]后移(i++)，如果非首位失配，则下次迭代只要从S[i]和P[next[j]]开始即可。因为在失配处的前面子串里，长度为next[j]的后缀是跟前缀一样的，这next[j]位必定是匹配的，无需再次迭代。
next数组求解
那么还剩下一个问题，next数组如何求解？
首先直观的方式是直接索引长度为1、2、3……的开头和结尾串，直到长度j-1的子串。其计算的重复性也是显而易见的。
较好的方法是使用动态规划。思考一下，当已知next[0...j]时，如何求出next[j+1]的值？
令k = next[j]，即从开头算起长度为j的子串，最长的相同前缀后缀长度为k。此时有两种情况：
- p[k] = p[j]：即之前的前后缀再往后看一格，也是相同的。所以此时这个长度就增加了1，即next[j+1] = k + 1。
p[k] ≠ p[j]：则令k = next[k]，即在原本的最长相同前缀子串里再寻找它的最长相同前缀，重复第一步。意思是说，对于p[j+1]，如果之前的相同前后缀再加一位是不相同的，那么再到这个前缀里去找，能不能找到？这样循环往复，直到最开始为止。
class Solution {
private:
int maxElement,lNULL, rNULL;
vector<int> sValues, tValues;
public:
void getMaxElement(TreeNode *p)
{
if(!p) return;
maxElement = max(maxElement, p->val);
getMaxElement(p->left);
getMaxElement(p->right);
}
void traverse(TreeNode * p, vector<int> & stack)
{
if(!p) return;
stack.push_back(p->val);
if(p->left == NULL)
stack.push_back(lNULL);
else
traverse(p->left, stack);
if(p->right == NULL)
stack.push_back(rNULL);
else
traverse(p->right, stack);
}
bool kmp()
{
int i = 0, j = 0;
int sLen = sValues.size(), tLen = tValues.size();
vector<int> next(tLen, 0);
//首先计算next数组
for(int k = 1; k < tLen; k++)
{
int index = k;
while(index > 0)
{
if(tValues[k] == tValues[next[index - 1]])
{
next[k] = next[index - 1] + 1;
break;
}
else
{
index = next[index - 1];
}
}
if(index <= 0) next[k] = 0;
}
//从头开始匹配字符串，失配后使用next数组重新尝试匹配
while(i < sLen && j < tLen)
{
if(j == 0)
{
while(sValues[i] != tValues[j] && i < sLen)
i++;
}
if(sValues[i] == tValues[j])
{
i++;
j++;
}
else
{
if(j > 0)
j = next[j - 1];
else
j = 0;
}
}
if(j == tLen)
return true;
return false;
}
bool isSubtree(TreeNode* s, TreeNode* t) {
maxElement = INT_MIN;
getMaxElement(s); //找出s和t中的最大值，分别+1 +2作为左右NULL值
getMaxElement(t);
lNULL = maxElement + 1;
rNULL = maxElement + 2;
traverse(s, sValues); //对s，t进行前序遍历
traverse(t, tValues);
return kmp();
}
};
