题目描述
输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构, 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3
/ \
4 5
/ \
1 2
给定的树 B:
4
/
1
返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1:
输入:A = [1,2,3], B = [3,1]
输出:false
示例 2:
输入:A = [3,4,5,1,2], B = [4,1]
输出:true
限制:
0 <= 节点个数 <= 10000
算法1
在熟练掌握树的遍历上 进行比对即可
注意树中可能有相同值的节点 所以一个A的子树不等同B树,还要继续查找
C++ 代码
class Solution {
public:
bool compareTree(TreeNode* A, TreeNode* B)
{
if ((A == NULL && B != NULL)) {
return false;
}
if (( B == NULL)) return true;
if (A->val != B->val) return false;
return compareTree(A->left, B->left) && compareTree(A->right, B->right);
}
bool dfs(TreeNode* A, TreeNode* B) {
if (A == NULL) return false;
if (A->val == B->val && compareTree(A, B)) {
return true;
}
return dfs(A->left, B) || dfs(A->right, B);
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
if (A == NULL || B == NULL) return false;
return dfs(A, B);
}
};
巨巨,序列化树A和树B,然后用kmp比对,最后这个例子没过qaq
[10,12,6,8,3,11]
[10,12,6,8]
这样也是子结构嘛
哈哈 我也有这个想法 但是没去实现
你觉得这个不是子结构吗?
按照字符串比较 这个也应该过了啊 返回true
|10||12||8||3||6||11|
|10||12||8||6|
序列化后的结果,emm,觉得这两棵树的结构不是很和谐呀,单看12和6节点感觉就不一样了,还是逐个比较节点稳
B是根节点10 左节点右节点12 8 左节点12又有个左节点6.
在A树里面都能找到的
(竖线表示左,斜杠表示右)我画出来的B:
10
| \
12 6
|
8
树A:
10
| \
12 6
| \ |
8 3 11
leetcode上有树形结构可视化的选项,可以实时看到,这两棵树按照这样画觉得就不是具有相同子结构了,返回false
我们的理解偏差在于子结构和子树吧
B的每个节点都可以在A中找到 而且他们的父节点子节点关系都一致,这就是子结构吧
没错,是这个重点,那这样的话是我这个答是错的,这里序列化是求整个树是否能和某一个整个子树一致, tql%%%
二叉树序列化 默认 左节点和右节点的索引 是根节点的2n和2n+1.
那么你画图的那颗树 序列化是 10 12 6 8 和10 12 6 8 3 11 |
我觉得可以用KMP的
好吧 我发现错误了,可以进行字符串比对,根据n 2n 2n+1这样的规则遍历比对B树的节点
但是不能KMP 这么做确实效率太低了.
还有个方法就是B树的空节点作为万能适配符放入进行比对,但是效率太低。
bfs+dfs序列化过不了,kmp这种不科学,只用来判断整个树是否一样,包括左边是null或者右边是null的情况,比较严格,kmp+二叉树字符串效率的话应该是O(max(n, m))的趴,不低,但是得不到正确答案
还是逐个比对,这个是好解法