题目：输入两棵二叉树A和B，判断B是不是A的子结构
分析：根据数的遍历方法，首先想到的是采用递归的方式要更简单些，树A从根节点进行遍历，首先判断与B的根节点值是否相等，如果相等则进行递归遍历验证，否则验证树A的其他节点，直到所有的结点遍历完。
注意的就是指针是否为NULL，因为自己编程能力不好，所以有些很简单的也做了注释，方便以后自己理解。
//判断B是不是A的子树
struct BinaryTree{
BinaryTree * LeftT
BinaryTree * RightT
bool DoesHasSubTree(BinaryTree *pRoot1,BinaryTree *pRoot2);
bool HasSubTree(BinaryTree * pRoot1,BinaryTree * pRoot2)
//当结点不相同的时候怎么去遍历其他的结点呢？
//这里采用的方法是设置一个result，当result=false时候我们并不是直接结束程序，而是继续去遍历其他点，直到所有的点都遍历完
//这里hasSubTree函数主要是为了遍历结点，而真正进行匹配是由函数DoesHasSubTree来实现
bool result=false;
if(pRoot1!=NULL&&pRoot2!=NULL)
//除此之外的所有情况我们都认为是不包含子树的，条件是不能丢的
if(pRoot1-&m_value==pRoot2-&m_value)
//一旦查到有结点相同，就进行递归遍历进行匹配见下面函数
result=DoesHasSubTree(pRoot1,pRoot2)
//这个函数式递归函数，所以在里面还需要进行判断pRoot1-&m_value==pRoot2-&m_value是否相等
if(!result)
//遍历了根节点接下来从左子树开始遍历，（递归的作用是左子树变成根节点进行匹配。）有点类似深度优先搜索。
result=HasSubTree(pRoot1-&LeftTree,pRoot2);
if(!result)
//当所有左子树没有匹配到我们就开始匹配右子树，直到所有的结点遍历完。
result=HasSubTree(pRoot1-&RightTree,pRoot2);
return//返回最终的结果
bool DoesHasSubTree(BinaryTree *pRoot1,BinaryTree *pRoot2)
if(pRoot2==NULL)
//当子树遍历完的标志，可以遍历完说明过程中没有碰到false条件，也就是都是匹配的
return true;
if(pRoot1==NULL)
return false;
if(pRoot1-&m_value!=pRoot2-&m_value)
return false;
return DoesHasSubTree(pRoot1-&LeftTree,pRoot2-&LeftTree)&& DoesHasSubTree(pRoot1-&RightTree,pRoot2-&RightTree);
//用&&对左右两边都进行判断
阅读(...) 评论()他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
爱生活,爱户外,爱技术
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
阅读(817)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
在LOFTER的更多文章
loftPermalink:'',
id:'fks_',
blogTitle:'判断B树是不是A树的一颗子树',
blogAbstract:'问题定义：& & & & &输入两棵二叉树A和B，判断B是不是A的子结构。思路：& & & & 要查找树A中是否存在和树B结构一样的子结构，我们可以分成两步：第一步在树A中找到和B的根节点的值一样的节点R，第二步再判断A中以R为根节点的子树是不是包含和树B一样的结构。（关于建树部分可以参考：',
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:0,
publishTime:0,
permalink:'blog/static/',
commentCount:0,
mainCommentCount:0,
recommendCount:0,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'爱生活,爱户外,爱技术',
hmcon:'0',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}The page is temporarily unavailable
nginx error!
The page you are looking for is temporarily unavailable.
Please try again later.
Website Administrator
Something has triggered an error on your
This is the default error page for
nginx that is distributed with
It is located
/usr/share/nginx/html/50x.html
You should customize this error page for your own
site or edit the error_page directive in
the nginx configuration file
/etc/nginx/nginx.conf.输入两颗二叉树a，b，判断b是不是a的子结构_百度知道
输入两颗二叉树a，b，判断b是不是a的子结构
我有更好的答案
if (pRoot1-&left)&&HasSubtree(pRoot1-&right,pRoot2-&gt：bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
if (NULL == pRoot1)
== pRoot2-&val)
return HasSubtree(pRoot1-&right);
return HasSubtree(pRoot1-&
if (NULL == pRoot2)
left,pRoot2-&gt如果树中的节点的值不重复的话可以用如下代码，非常简洁
#include &iostream&struct TreeNode{
TreeNode *
TreeNode *
TreeNode(int value): val(value), left(NULL), right(NULL) { }};//Determine if binary tree root2 is a sub-structure of binary tree root1.bool SubBinaryTree(TreeNode *root1, TreeNode *root2){
if(!root1 && !root2)
if(root1 && root2){
if(root1-&val == root2-&val)
return SubBinaryTree(root1-&left, root2-&left) &&
SubBinaryTree(root1-&right, root2-&right);
return SubBinaryTree(root1-&left, root2) ||
SubBinaryTree(root1-&right, root2);
}挺有意思的一个题目。
为您推荐：
其他类似问题
二叉树的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。