572、另一棵树的子树
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
3
/ \
4 5
/ \
1 2
给定的树 t：
4
/ \
1 2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s：
3
/ \
4 5
/ \
1 2
/
0
给定的树 t：
4
/ \
1 2
返回 false。
题解
1、先序遍历搜索
对源树进行先序遍历，然后对于每一个节点进行优先遍历匹配。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
// 先序遍历匹配函数
private boolean check(TreeNode s,TreeNode t) {
// 都为空
if (s == null && t == null) {
return true;
}
// 值比较
if ((s == null && t != null) || (s != null && t == null) || (s.val != t.val)) {
return false;
}
// 先序遍历
return check(s.left,t.left) && check(s.right,t.right);
}
private boolean preTraverse(TreeNode s,TreeNode t) {
// 源树为空
if (s == null) {
return false;
}
// 先序遍历搜索匹配的结果
return check(s,t) || preTraverse(s.left,t) || preTraverse(s.right,t);
}
public boolean isSubtree(TreeNode s, TreeNode t) {
return preTraverse(s,t);
}
}
2、序列化 和 串匹配
- 将二叉树的节点及其空叶子节点序列化
class Solution {
public:
vector <int> sOrder, tOrder;
int maxElement, lNull, rNull;
void getMaxElement(TreeNode *o) {
if (!o) return;
maxElement = max(maxElement, o->val);
getMaxElement(o->left);
getMaxElement(o->right);
}
void getDfsOrder(TreeNode *o, vector <int> &tar) {
if (!o) return;
tar.push_back(o->val);
if (o->left) getDfsOrder(o->left, tar);
else tar.push_back(lNull);
if (o->right) getDfsOrder(o->right, tar);
else tar.push_back(rNull);
}
bool kmp() {
int sLen = sOrder.size(), tLen = tOrder.size();
vector <int> fail(tOrder.size(), -1);
for (int i = 1, j = -1; i < tLen; ++i) {
while (j != -1 && tOrder[i] != tOrder[j + 1]) j = fail[j];
if (tOrder[i] == tOrder[j + 1]) ++j;
fail[i] = j;
}
for (int i = 0, j = -1; i < sLen; ++i) {
while (j != -1 && sOrder[i] != tOrder[j + 1]) j = fail[j];
if (sOrder[i] == tOrder[j + 1]) ++j;
if (j == tLen - 1) return true;
}
return false;
}
bool isSubtree(TreeNode* s, TreeNode* t) {
maxElement = INT_MIN;
getMaxElement(s);
getMaxElement(t);
lNull = maxElement + 1;
rNull = maxElement + 2;
getDfsOrder(s, sOrder);
getDfsOrder(t, tOrder);
return kmp();
}
};
> 链接：https://leetcode-cn.com/problems/subtree-of-another-tree/solution/ling-yi-ge-shu-de-zi-shu-by-leetcode-solution/
3、树哈希法
构造下面的哈希函数：
$$ f_o = v_o + 31·f_l·p(s_l)+179·f_r·p(s_r)$$
这里 $f_x$ 表示节点 x 的哈希值，$s_x$ 表示节点 x 对应的子树大小，$v_x$ 代表节点 x 的 val，$p(n)$ 表示第 n 个素数，o 表示当前节点，l和 r 分别表示左右孩子。
class Solution {
public:
static constexpr int MAX_N = 1000 + 5;
static constexpr int MOD = int(1E9) + 7;
bool vis[MAX_N];
int p[MAX_N], tot;
void getPrime() {
vis[0] = vis[1] = 1; tot = 0;
for (int i = 2; i < MAX_N; ++i) {
if (!vis[i]) p[++tot] = i;
for (int j = 1; j <= tot && i * p[j] < MAX_N; ++j) {
vis[i * p[j]] = 1;
if (i % p[j] == 0) break;
}
}
}
struct Status {
int f, s; // f 为哈希值 | s 为子树大小
Status(int f_ = 0, int s_ = 0)
: f(f_), s(s_) {}
};
unordered_map <TreeNode *, Status> hS, hT;
void dfs(TreeNode *o, unordered_map <TreeNode *, Status> &h) {
h[o] = Status(o->val, 1);
if (!o->left && !o->right) return;
if (o->left) {
dfs(o->left, h);
h[o].s += h[o->left].s;
h[o].f = (h[o].f + (31LL * h[o->left].f * p[h[o->left].s]) % MOD) % MOD;
}
if (o->right) {
dfs(o->right, h);
h[o].s += h[o->right].s;
h[o].f = (h[o].f + (179LL * h[o->right].f * p[h[o->right].s]) % MOD) % MOD;
}
}
bool isSubtree(TreeNode* s, TreeNode* t) {
getPrime();
dfs(s, hS);
dfs(t, hT);
int tHash = hT[t].f;
for (const auto &[k, v]: hS) {
if (v.f == tHash) {
return true;
}
}
return false;
}
};
> 链接：https://leetcode-cn.com/problems/subtree-of-another-tree/solution/ling-yi-ge-shu-de-zi-shu-by-leetcode-solution/
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
