首页 > 代码库 > careercup-树与图 4.8
careercup-树与图 4.8
4.8 你有两棵非常大的二叉树：T1，有几百万个结点；T2，有几百个结点。设计一个算法，判断T2是否为T1的子树。
如果T1有这么一个结点n，其子树与T2一模一样，则T2是T1的子树。也就是说，从结点n处把树砍掉，得到的树与T2完全相同。
C++实现代码：
#include<iostream>#include<new>#include<cmath>using namespace std;//Definition for binary treestruct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};void createTree(TreeNode *&root){ int i; cin>>i; if(i!=0) { TreeNode *tmp=new TreeNode(i); root=tmp; createTree(root->left); createTree(root->right); }}bool isSubTree(TreeNode *root1,TreeNode *root2){ //root2为空时是任何数的子树 if(root2==NULL) return true; //如果root2不为空，但是root1为空，则返回false if(root1==NULL) return false; if(root1->val==root2->val) return isSubTree(root1->left,root2->left)&&isSubTree(root1->right,root2->right); else return isSubTree(root1->left,root2)||isSubTree(root1->right,root2); return false;}int main(){ TreeNode *root1=NULL; TreeNode *root2=NULL; createTree(root1); createTree(root2); cout<<isSubTree(root1,root2)<<endl;}
careercup-树与图 4.8
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。