题目描述

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

样例

给定的树 s:

     3
    / \
   4   5
  / \
 1   2
给定的树 t：

   4 
  / \
 1   2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。

算法1

(暴力DFS) $O(nm)$

就是暴力，假设s有n个节点，在每个节点查看子树是否与t一样即可。

时间复杂度

遍历n个节点，假设t有m个节点，每次检查子树是否与t一致需要m次操作，时间复杂度为$O(nm)$。

参考文献

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (!s && !t) return true;
        if (!s) return false;
        return dfs(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);
    }

    bool dfs(TreeNode * s, TreeNode *t){
        if (!s && !t) return true;
        if (!t || !s || s->val != t->val) return false;
        return dfs(s->left, t->left) && dfs(s->right, t->right);
    }
};

算法2

(序列化 + KMP) $O(n + m)$

将s和t均序列化，再在s序列中查找是否有子序列t；
注意，为了避免一些同元素异结构的树造成错误的匹配，叶子节点的空节点也要加入序列。

时间复杂度

序列化时间复杂度为$O(n + m)$，
KMP时间复杂度还是$O(n + m)$。
当然这里时间复杂度是渐进的，由于数据规模小，其实并看不出性能上的优势。

参考文献

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int max_val = INT_MIN;
    int lnull, rnull;
    vector<int> s_serial, t_serial;
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (!s && !t) return true;
        if (!t) return false;
        getmax(s); getmax(t);
        lnull = max_val + 1, rnull = max_val + 2;

        serialize(s, s_serial);
        serialize(t, t_serial);

        return kmp(s_serial, t_serial);
    }

    bool kmp(vector<int> &s, vector<int> &t){
        int m = s.size(), n = t.size();
        vector<int> next_ = getNext(t);
        int i = 0, j = 0;
        while (i < m && j < n){
            if (j < 0 || s[i] == t[j]) ++i, ++j;
            else j = next_[j];
        }
        return j == n;
    }

    vector<int> getNext(vector<int> &target){
        int n = target.size();
        int j = 0, t = -1;
        vector<int> next_(n); next_[0] = -1;

        while (j < n - 1){
            if (t < 0 || target[j] == target[t]){
                ++j; ++t; next_[j] = t;
            }
            else t = next_[t];
        }
        return next_;
    }

    void getmax(TreeNode *node){
        if (!node) return;
        max_val = max(max_val, node->val);
        getmax(node->left); getmax(node->right);
    }

    void serialize(TreeNode * node, vector<int> &memo){
        if (!node) return;

        memo.push_back(node->val);
        if (node->left) serialize(node->left, memo);
        else memo.push_back(lnull);
        if (node->right) serialize(node->right, memo);
        else memo.push_back(rnull);

    }
};