题解 | #树的子结构#
树的子结构
https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88
解答：首先因为结点值可能重复，所以得考虑双递归，一个递归遍历所有结点，一个递归判断是否是子结构，因此时间复杂度为O(n^2)，空间复杂度为O(1)。注意当成功找到一个以后得保存答案或者直接返回，要不然可能后续还有点的值相等但不是子结构，会将答案改为false。
class Solution {
public:
bool res=false,tmp;
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
if(pRoot2==NULL||pRoot1==NULL){return false;}
dfs_in(pRoot1,pRoot2);
return res;
}
void dfs_in(TreeNode* root1,TreeNode* root2){
if(root1==NULL){
return;
}
if(root1->val==root2->val){
tmp=true;
dfs(root1,root2);
if(tmp==true){
res=true;
}
}
dfs_in(root1->left,root2);
dfs_in(root1->right,root2);
}
void dfs(TreeNode* root1,TreeNode* root2){
if(root1==NULL&&root2==NULL){
return;
}
if(root1!=NULL&&root2==NULL){
return;
}
if(root1==NULL&&root2!=NULL){
tmp=false;
return;
}
if(root1->val!=root2->val){
tmp=false;
return;
}
dfs(root1->left,root2->left);
dfs(root1->right,root2->right);
}
};
TP-LINK三面22人在聊
查看6道真题和解析