首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一棵二元树的根结点,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 输出该树的深度3。 二元树的结点定义如下: struct SBinaryTreeNode // a node of the
输入一棵二元树的根结点,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 输出该树的深度3。 二元树的结点定义如下: struct SBinaryTreeNode // a node of the
admin
2019-03-29
139
问题
输入一棵二元树的根结点,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
输出该树的深度3。
二元树的结点定义如下:
struct SBinaryTreeNode // a node of the binary tree
{
int m_nValue; // value of node
SBinaryTreeNode *m_pLeft; // left child of node
SBinaryTreeNode *m_pRight; // right child of node
};
选项
答案
/////////////////////////////////////////////////////////////////////// // Get depth of a binary tree // Input: pTreeNode - the head of a binary tree // Output: the depth of a binary tree /////////////////////////////////////////////////////////////////////// int TreeDepth(SBinaryTreeNode *pTreeNode) { // the depth of a empty tree is 0 if(!pTreeNode) return 0; // the depth of left sub-tree int nLeft = TreeDepth(pTreeNode->m_pLeft); // the depth of right sub-tree int nRight = TreeDepth(pTreeNode->m_pRight); // depth is the binary tree return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1); }
解析
这道题本质上还是考查二元树的遍历。
题目给出了一种树的深度的定义。当然,我们可以按照这种定义去得到树的所有路径,也就能得到最长路径以及它的长度。只是这种思路用来写程序有点麻烦。
我们还可以从另外一个角度来理解树的深度。如果一棵树只有一个结点,它的深度为1。如果根结点只有左子树而没有右子树,那么树的深度应该是其左子树的深度加1;同样如果根结点只有右子树而没有左子树,那么树的深度应该是其右子树的深度加1。如果既有右子树又有左子树呢?那该树的深度就是其左、右子树深度的较大值再加1。
上面的这个思路用递归的方法很容易实现,只需要对遍历的代码稍作修改即可。
转载请注明原文地址:https://kaotiyun.com/show/cRmZ777K
0
程序员面试
相关试题推荐
Inthissection,youareaskedtowriteanessaybasedonthefollowinginformation.Makecommentsandexpressyourownopinion.
Directions:Inthissection,youareaskedtowriteanessaybasedonthefollowinginformation.Makecommentsandexpressy
ASP.net的身份验证方式有哪些?分别是什么原理?
两个单向链表,找出它们的第一个公共结点。链表的结点定义为:structListNode{intm_nKey;ListNode*m_pNext;};
输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下:structListNode{intm_nKey;ListNode*m_pNext;};
使用.NETPassport向导注册MSN帐户,姓名为李明,邮件的地址为liming@hotmail.com,密码为123456lm。
在当前界面【管理工具】窗口中,设置Windows密码策略,将密码长度最小值设置为8个字符。
在控制面板中,将鼠标的"右手习惯"改为"左手习惯"。
在PPoint中,超级链接只有在()中起作用。A.幻灯片视图B.幻灯片放映C.幻灯片浏览视图D.大纲视图
Excel2000中,列标()A.可以用各种符号表示B.用数字表示C.用字母表示D.可以用中文文字表示
随机试题
具有四级结构的蛋白质特征是
血浆中起关键作用的缓冲对是
疾病监测采用的方法属于
关于一般抹灰施工及基层处理的说法,错误的是()。
我国雨凇最多的地方是()。
材料:刘某是一名初中二年级的学生,他特别喜欢罗纳尔多,于是把头发剃成足球式的形状。第二天来学校上课,刚走进教室,被老师看见,老师便对他说:“你的发式太怪了,把头发再剪剪,恢复正常了再来上课,顺便让你爸爸妈妈来学校一趟。”刘某回家后,将这件事告知家人,第二
一个人应该活得是自己并且干净顾城人的生命里有一种能量,它使你不安宁。说它是欲望也行,幻想也行,妄想也行,总之它不可能停下来,它需要一
A、 B、 C、 D、 A图形中的外层四边形顺时针旋转45。、中间四边形顺时针旋转90。、内部四边形逆时针旋转45。,得到后一个图形。由此应选择A。
根据下述材料。写一篇700字左右的论说文,题目自拟。中心是令人向往的地方,处于中心地带往往有诸多便利、机会和认同。当然也有人在中心地带迷失,最终边缘化。边缘是让人平静的地方,它的质朴和别样让生活其中的人受益良多,甚至还吸引中心的人们探寻它的魅力。
Weliveinatimewhen,morethaneverbeforeinhistory,peoplearemovingabout.
最新回复
(
0
)