题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
第一想法
- 如何遍历二叉树？
前中后序遍历
- 如何判断子结构？
- 前序遍历结果相等就可以证明子结构了吗？（需不需要两种遍历同时符合，因为之前一题还原需要两种遍历序列）
- 比较子串我想到了KMP算法（字符子串和数字子串一样吗）
需要两种遍历结果
XXX 缺乏树遍历的知识
代码如下,还是很长,且无法通过
思路是返回AB两树的前序和中序遍历序列,各自有从属关系时则是子结构.
后来仔细想了想,虽然前序+中序能够确定一个二叉树,但是不能确定子结构的从属关系,如下:
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
vector<int> tree1pre, tree1in, tree2pre, tree2in;
inTree(pRoot1, tree1in);
preTree(pRoot1, tree1pre);
inTree(pRoot2, tree2in);
preTree(pRoot2, tree2pre);
int k,m = 0;
bool flag1 = false;
bool flag2 = false;
for(int i = 0; i < tree1pre.size(); i++){
if(tree1pre[i] == tree2pre[0]){
k = i;
for(int j = 0; j < tree2pre.size(); j++){
if(tree1pre[k] == tree2pre[j]){
m++;
k++;
if(m == tree2pre.size())
flag1 = true;
}
else{
m = 0;
break;
}
}
}
}
m = 0;
for(int i = 0; i < tree1in.size(); i++){
if(tree1in[i] == tree2in[0]){
k = i;
for(int j = 0; j < tree2in.size(); j++){
if(tree1in[k] == tree2in[j]){
m++;
k++;
if(m == tree2in.size())
flag2 = true;
}
else{
m = 0;
break;
}
}
}
}
return flag1 && flag2;
}
void inTree(TreeNode* pRoot, vector<int>& tree){
if(pRoot == NULL) return;
else{
inTree(pRoot -> left, tree);
tree.push_back(pRoot -> val);
inTree(pRoot -> right, tree);
}
}
void preTree(TreeNode* pRoot, vector<int>& tree){
if(pRoot == NULL) return;
else{
tree.push_back(pRoot -> val);
preTree(pRoot -> left, tree);
preTree(pRoot -> right, tree);
}
}
};
这一版的程序在我自己的Vscode上通过测试.完成依据两种遍历数组的从属关系返回True或False,对树2长度>树1的情况还没做处理,我觉得是基本完成了.但没有AC,两个循环O(n^2)时间复杂度也比较高了
- 原本也想过直接对树进行比较
- 原本也想过用递归实现
?为什么拒绝直接对树进行比较的方法
因为想着从root向下,遇到的第一个结点val相等,万一不是,还要if讨论,再往下遇到第二个结点与子结构的相等,又多出一个分支,加之没有之前对树进行比较的经验,让我把它化为vector再处理.
?为什么放弃递归实现
因为想着传递上来的应该是一个值而非布尔变量,想着可能无法用递归实现.
不是很能理解递归是因为思路总是由顶向下而非递归的由底往上
我再用递归试试.
如果使用if pRoot == NULL --- return false作为递归基,那么就不会有return true的情况
看了讨论我发现问题是我本想以一个函数的递归来解决任务.结果其实是分为找到开始遍历的根节点和看子树是否一致这两个函数来做的.原来的代码 ↓
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot1 == NULL) return false;
if(pRoot2 == NULL) return true;
else{
if(pRoot1 -> val == pRoot2 -> val)
return HasSubtree(pRoot1 -> left, pRoot2 -> left) && HasSubtree(pRoot1 -> right, pRoot2 -> right);
else{
return HasSubtree(pRoot1 -> left, pRoot2) || HasSubtree(pRoot1 -> right, pRoot2);
}
}
}
AC的代码
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot1 == NULL || pRoot2 == NULL ) return false;
/*以下四行改成第二行一行也可以通过*/
if(pRoot1 -> val == pRoot2 -> val)
return IsSubTree(pRoot1, pRoot2) || HasSubtree(pRoot1 -> left, pRoot2) || HasSubtree(pRoot1 -> right, pRoot2);
else{
return HasSubtree(pRoot1 -> left, pRoot2) || HasSubtree(pRoot1 -> right, pRoot2);
}
}
private:
bool IsSubTree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot2 == NULL)//需要注意的是这个要写在前面,因为当两树原本一致都遍历到底部,同为NULL,应该返回true.
return true;
if(pRoot1 == NULL)
return false;
if(pRoot1 -> val == pRoot2 -> val)
return IsSubTree(pRoot1 -> left, pRoot2 -> left) && IsSubTree(pRoot1 -> right, pRoot2 -> right);
else{
return false;
}
}
};
可是为什么要把他们分开来呢?不分开我又重新改了第一遍递归的代码
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot2 == NULL) return true;
if(pRoot1 == NULL) return false;
else{
if(pRoot1 -> val == pRoot2 -> val)
return HasSubtree(pRoot1 -> left, pRoot2 -> left) && HasSubtree(pRoot1 -> right, pRoot2 -> right) || HasSubtree(pRoot1 -> left, pRoot2) || HasSubtree(pRoot1 -> right, pRoot2);
else{
return HasSubtree(pRoot1 -> left, pRoot2) || HasSubtree(pRoot1 -> right, pRoot2);
}
}
}
};
通过率是70%
问题出在哪了呢?
用例:
{8,#,9,3,2},{}
对应输出应该为:
false
你的输出为:
true
本函数的递归无法辨别proot2是到底了还是根本本来就是NULL
所以将遍历到值相等与比较分开.
最简洁的代码
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot1 == NULL || pRoot2 == NULL ) return false;
return IsSubTree(pRoot1, pRoot2) || HasSubtree(pRoot1 -> left, pRoot2) || HasSubtree(pRoot1 -> right, pRoot2);
}
private:
bool IsSubTree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot2 == NULL) return true;
if(pRoot1 == NULL) return false;
return pRoot1 -> val == pRoot2 -> val && IsSubTree(pRoot1 -> left, pRoot2 -> left) && IsSubTree(pRoot1 -> right, pRoot2 -> right);
}
};
本题主要的坑是一个函数的递归基不满足条件.
