分享程序员开发的那些事...
更新时间：2022-08-22 08:32:17
4.8 你有两棵非常大的二叉树：T1，有几百万个结点；T2，有几百个结点。设计一个算法，判断T2是否为T1的子树。
如果T1有这么一个结点n，其子树与T2一模一样，则T2C++实现代码：
#include<iostream> #include<new> using namespace std; //Definition for binary tree struct 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 isSub(TreeNode *n1,TreeNode *n2) { if(n1==NULL) return false; if(n1==n2) return true; if(n1->val!=n2->val) return false; return isSub(n1->left,n2->left)&&isSub(n1->right,n2->right); } bool isSubTree(TreeNode *root1,TreeNode *root2) { bool result=false; if(root1&&root2) { if(root1->val==root2->val) result=isSub(root1,root2); if(!result) result=isSubTree(root1->left,root2); if(!result) result=isSubTree(root1->right,root2); } return result; } int main() { TreeNode *root1=NULL; TreeNode *root2=NULL; createTree(root1); createTree(root2); cout<<isSubTree(root1,root2)<<endl; }