[E二叉树] lc572. 另一棵树的子树(dfs+前中序判断+树哈希+树上KMP+好题)

1. 题目来源

链接：572. 另一棵树的子树

2. 题目解析

看到这个题目就感觉不简单，因为写了写 dfs 版本的，发现好像不太会…

还是简单粗暴一点，直接搞一个 前序+中序，进行判断即可。我们知道通过 前序+中序，是可以构建出一颗唯一的二叉树的，当然可以通过 前序+中序，去判断两颗二叉树是不是一样的。

但这里需要注意的是：

• 我们需要将 NULL 的位置也通过占位标记记录一下，不然无法判断子树完全相等，只能判断出来存在相同的子结构。例如：
• 
  
  但这里需要判断两个 vector a、b，b 是否在 a 中出现…这个东西写起来比较耗性能。但在这还是过了。算是一个思路吧。

---

dfs：
每个点，都可能是目标子树的根节点，同时我们需要判断当根节点确定时，该根节点的子树是否等于目标子树。故需要两个递归函数：

• dfs 函数：遍历树上所有节点，判断以该节点作为根节点，它的子树是否有包含目标子树。
  • 先判断当前根节点是否可以作为目标子树的根节点。
  • 再判断根节点的左子树、右子树下的所有节点是否可以作为目标子树的根节点。
• check 函数：判断节点所处子树是否等于目标子树。

---

至于其他的写法，看官解吧。还是很秀的…

评论区有提到 树上 HASH 的方法字节面试过…让写一下…

---

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

前、中 序判断二叉树。

/*** 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:vector<int> a1, a2, b1, b2;void dfs1(TreeNode* root, vector<int> &v) {if (!root) {v.push_back(1e9); return;}v.push_back(root->val);dfs1(root->left, v);dfs1(root->right, v);}void dfs2(TreeNode* root, vector<int> &v) {if (!root) {v.push_back(1e9); return;}dfs2(root->left, v);v.push_back(root->val);dfs2(root->right, v);}bool check(vector<int> &a, vector<int>& b) {int n = a.size(), m = b.size();for (int i = 0; i < n; i ++ ) {bool flag = false;for (int k = i, j = 0; k < n && j < m; j ++ , k ++ ) {if (a[k] != b[j]) {break;}if (j == m - 1) flag = true;}if (flag) return true;}return false;}bool isSubtree(TreeNode* root, TreeNode* subRoot) {dfs1(root, a1);dfs2(root, a2);dfs1(subRoot, b1);dfs2(subRoot, b2);return check(a1, b1) && check(a2, b2);}
};

dfs：

/*** 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 check(TreeNode* root, TreeNode* subRoot) {if (!root && !subRoot) return true;if (!root && subRoot) return false;if (root && !subRoot) return false;if (root->val != subRoot->val) return false;// 同步判断子结构是否一致return check(root->left, subRoot->left) && check(root->right, subRoot->right);}// 判断树 root 下是否存在 subRoot 结构的子树bool dfs(TreeNode* root, TreeNode* subRoot) {if (!root) return false;// 先判断root根是否可以作为目标子树的根// root根无法作为目标子树根，目标子树根可能存在root的左子树、右子树当中// dfs 判断左子树 是否存在目标子树// dfs 判断右子树 是否存在目标子树return check(root, subRoot) || dfs(root->left, subRoot) || dfs(root->right, subRoot);}bool isSubtree(TreeNode* root, TreeNode* subRoot) {return dfs(root, subRoot);}
};