首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一棵二元树的根结点,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 输出该树的深度3。 二元树的结点定义如下: struct SBinaryTreeNode // a node of the
输入一棵二元树的根结点,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 输出该树的深度3。 二元树的结点定义如下: struct SBinaryTreeNode // a node of the
admin
2019-03-29
104
问题
输入一棵二元树的根结点,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
输出该树的深度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
程序员面试
相关试题推荐
Publicationbiasinacademicjournalsisnothingnew.Afindingofnocorrelationbetweensportingeventsandeitherviolentcri
求1+2+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句(A?B:C)。
输入n个整数,输出其中最小的k个。例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。
输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4
游标的作用?如何知道游标已经到了最后?
在控制面板中,将鼠标的"右手习惯"改为"左手习惯"。
在字体对话框中不能设置()A.字体B.字号C.字符间距D.文字样式
计算机能直接识别和执行的语言是()A.机器语言B.高级语言C.数据库语言D.汇编程序
关系型数据库只能描述()关系。A.网络型B.二维表格C.图D.层次型
软盘写保护的作用是()。A.防止持签B.防止读盘C.防止显示D.防止写盘
随机试题
对于因胎盘植入导致的产后出血,应立即采取的措施是()
Wewerelateasusual.Myhusbandhad【C1】______wateringtheflowersinthegardenbyhimself,andwhenhediscoveredthathecou
维生素C又名抗坏血酸,其产生酸性的结构原因是
施工机械工作时间中的不可避免的无负荷工作时间应属于()。若该工程,承包商以自有机械设备施工,期间由于业主原因导致停工,则承包商计算窝工费向业主提出索赔时应按()。
行政复议机关责令被申请人重新作出具体行政行为,法律、法规、规章未规定期限的,重新作出具体行政行为的期限为()日。
公文的成文时间是指它的印制时间。()
教师职业道德使教师在职业生活中具有积极性、主动性和创造性,能促使教师不断加强自我修养、自我发展和自我完善,自觉地做好教育工作。这体现了教师职业道德具有()。
Inspiteof"endlesstalkofdifference,"Americansocietyisanamazingmachineforhomogenizingpeople.Thereis"thedemocra
ThepollutionquestionaswellasotherissuesisgoingtobediscussedwhentheCongressisin______againnextspring.
重阳节农历九月九日是传统的重阳节,或者说是双九节。登高避邪的习俗从很久以前就流传下来。因此,重阳节也被称为“登高节”。1989年,中国政府决定把重阳节定为老年节。从那以后,所有政府单位、组织和街道社区每年都会为退休职工组织一次秋游。在水边或山间,
最新回复
(
0
)