给定两个非空二叉树 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。此时有两种情况：

1. p[k] = p[j]：即之前的前后缀再往后看一格，也是相同的。所以此时这个长度就增加了1，即next[j+1] = k + 1。

2. p[k] ≠ p[j]：则令k = next[k]，即在原本的最长相同前缀子串里再寻找它的最长相同前缀，重复第一步。意思是说，对于p[j+1]，如果之前的相同前后缀再加一位是不相同的，那么再到这个前缀里去找，能不能找到？这样循环往复，直到最开始为止。

   class Solution {
   private:
   int maxElement,lNULL, rNULL;
   vector 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-&gt;left == NULL)
       stack.push_back(lNULL);
   else
       traverse(p-&gt;left, stack);
   
   if(p-&gt;right == NULL)
       stack.push_back(rNULL);
   else
       traverse(p-&gt;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 &lt; tLen; k++)
   {
       int index = k;
       while(index &gt; 0)
       {
           if(tValues[k] == tValues[next[index - 1]])
           {
               next[k] = next[index - 1] + 1;
               break;
           }
           else
           {
               index = next[index - 1];
           }
       }
       if(index &lt;= 0) next[k] = 0;
   }
   
   //从头开始匹配字符串，失配后使用next数组重新尝试匹配
   while(i &lt; sLen &amp;&amp; j &lt; tLen)
   {
       if(j == 0)
       {
           while(sValues[i] != tValues[j] &amp;&amp; i &lt; sLen)
               i++;
       }
   
       if(sValues[i] == tValues[j])
       {
           i++;
           j++;
       }
       else
       {
           if(j &gt; 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();
   }

   };