题目

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：
image.png

  1. 输入：root = [3,4,5,1,2], subRoot = [4,1,2]
  2. 输出：true

示例 2：
image.png

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

提示：

  • root 树上的节点数量范围是 [1, 2000]
  • subRoot树上的节点数量范围是 [1, 1000]
  • -10^4 <= root.val <= 10^4

  • -10^4 <= subRoot.val <= 10^4

    解题方法

    DFS+暴力搜索

    通过 DFS 遍历二叉树的节点，对每个节点进行暴力搜索。
    时间复杂度O(s*t)，空间复杂度O(max(ds,dt))
    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 compare(TreeNode* left, TreeNode* right) {
      if(!left && right)  return false;
      else if(!right && left)  return false;
      else if(!left && !right) return true;
      else if(left->val != right->val)    return false;
      else return compare(left->right, right->right) && compare(left->left, right->left);
  }

  bool isSubtree(TreeNode* root, TreeNode* subRoot) {
      if(!root)   return false;
      return compare(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
  }
};

    DFS+KMP

    通过 DFS 获取二叉树的前序遍历序列，其中空子树通过INT_MAX替代。再通过 KMP 进行匹配。
    时间复杂度O(s+t)，空间复杂度O(s+t)
    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:
  void get_dfsorder(TreeNode* s, vector<int> &order) {
      if(!s)  return;
      order.push_back(s->val);
      if(s->left)     get_dfsorder(s->left, order);
      else    order.push_back(INT_MAX);
      if(s->right)    get_dfsorder(s->right, order);
      else    order.push_back(INT_MAX);
  }

  vector<int> getNext(vector<int> p) {
      int size = p.size();
      vector<int> next;
      next.push_back(0);
      int i = 0, j = 1;
      while(j<size) {
          if(p[i]==p[j]) {
              i++;
              next.push_back(i);
              j++;
          }
          else {
              if(i>0)    i = next[i-1];
              else {
                  next.push_back(i);
                  j++;
              }
          }
      }

      return next;
  }

  bool KMP(vector<int> s, vector<int> p) {
      int s_size = s.size();
      int p_size = p.size();

      if(s_size<p_size)   return false;

      vector<int> next = getNext(p);

      int i=0, j=0, head=0;
      while(head<=s_size-p_size && i<s_size) {
          if(s[i]==p[j]) {
              i++;
              j++;
          }
          else {
              if(j>0) {
                  head += j-next[j-1];
                  j = next[j-1];
              }
              else {
                  i++;
                  head++;
              }
          }
          if(j==p_size)   return true;
      }

      return false;
  }

  bool isSubtree(TreeNode* root, TreeNode* subRoot) {
      if(!root)   return false;
      vector<int> s_order, p_order;
      get_dfsorder(root, s_order);
      get_dfsorder(subRoot, p_order);
      return KMP(s_order, p_order);
  }
};

    哈希法

    对构建哈希函数，通过节点值等确定子树对应的哈希值，从而进行查找。