子树中是否有另一棵子树

力扣官方题解: 深度优先搜索序列上做串匹配

这个方法需要我们先了解一个「小套路」：一棵子树上的点在深度优先搜索序列（即先序遍历）中是连续的。了解了这个「小套路」之后，我们可以确定解决这个问题的方向就是：把 sss 和 ttt 先转换成深度优先搜索序列，然后看 ttt 的深度优先搜索序列是否是 sss 的深度优先搜索序列的「子串」。

这样做正确吗？ 假设 sss 由两个点组成，111 是根，222 是 111 的左孩子；ttt 也由两个点组成，111 是根，222 是 111 的右孩子。这样一来 sss 和 ttt 的深度优先搜索序列相同，可是 ttt 并不是 sss 的某一棵子树。由此可见「sss 的深度优先搜索序列包含 ttt 的深度优先搜索序列」是「ttt 是 sss 子树」的必要不充分条件，所以单纯这样做是不正确的。

为了解决这个问题，我们可以引入两个空值 lNull 和 rNull，当一个节点的左孩子或者右孩子为空的时候，就插入这两个空值，这样深度优先搜索序列就唯一对应一棵树。处理完之后，就可以通过判断「sss 的深度优先搜索序列包含 ttt 的深度优先搜索序列」来判断答案。

在判断「sss 的深度优先搜索序列包含 ttt 的深度优先搜索序列」的时候，可以暴力匹配，也可以使用 KMP 或者 Rabin-Karp 算法，在使用 Rabin-Karp算法的时候，要注意串中可能有负值。

这里给出用 KMP 判断的代码实现。

class Solution {
public:
    vector <int> sOrder, tOrder;
    int maxElement, lNull, rNull;
    // 获取树中的最大值.
    void getMaxElement(TreeNode *node) {
        if (!node) return;
        maxElement = max(maxElement, node->val);
        getMaxElement(node->left);
        getMaxElement(node->right);
    }
    //深度优先搜索遍历
    void getDfsOrder(TreeNode *node, vector <int> &tar) {
        if (!node) return;
        tar.push_back(node->val);
        if (node->left) getDfsOrder(node->left, tar);
        else tar.push_back(lNull);
        if (node->right) getDfsOrder(node->right, tar);
        else tar.push_back(rNull);
    }

    bool kmp() {
        int sLen = sOrder.size(), tLen = tOrder.size();
        vector <int> next(tOrder.size(), -1);
        // 生成模式串跳转数组
        for (int i = 1, j = -1; i < tLen; ++i) {
            while (j != -1 && tOrder[i] != tOrder[j + 1]) 
                j = next[j];
            if (tOrder[i] == tOrder[j + 1]) ++j;
            next[i] = j;
        }
        for (int i = 0, j = -1; i < sLen; ++i) {
            while (j != -1 && sOrder[i] != tOrder[j + 1])
                j = next[j];
            if (sOrder[i] == tOrder[j + 1]) ++j;
            if (j == tLen - 1) return true;
        }
        return false;
    }

    bool isSubtree(TreeNode* s, TreeNode* t) {
        // 初始化lNull和rNull, 为深度遍历做准备
        maxElement = INT_MIN;
        getMaxElement(s);
        getMaxElement(t);
        lNull = maxElement + 1;
        rNull = maxElement + 2;

        getDfsOrder(s, sOrder);
        getDfsOrder(t, tOrder);

        return kmp();
    }
};