首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 则打印出两条路径:10, 12和10, 5, 7。 二元树结点的数据结构定义为: struct
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 则打印出两条路径:10, 12和10, 5, 7。 二元树结点的数据结构定义为: struct
admin
2019-03-29
135
问题
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
例如输入整数22和如下二元树
则打印出两条路径:10, 12和10, 5, 7。
二元树结点的数据结构定义为:
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
选项
答案
/////////////////////////////////////////////////////////////////////// // Find paths whose sum equal to expected sum /////////////////////////////////////////////////////////////////////// void FindPath ( BinaryTreeNode* pTreeNode, // a node of binary tree int expectedSum, // the expected sum std::vector
&path, // a pathfrom root to current node int& currentSum // the sum of path ) { if(!pTreeNode) return; currentSum += pTreeNode->m_nValue; path.push_back(pTreeNode->m_nValue); // if the node is a leaf, and the sum is same as pre-defined, // the path is what we want. print the path bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight); if(currentSum == expectedSum && isLeaf) { std::vector
::iterator iter =path.begin(); for(; iter != path.end(); ++ iter) std::cout<<*iter<<’\t’; std::cout<
m_pLeft) FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum); if(pTreeNode->m_pRight) FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum); // when we finish visiting a node and return to its parent node, // we should delete this node from the path and // minus the node’s value from the current sum currentSum -= pTreeNode->m_nValue; //!!I think here is no use path.pop_back(); }
解析
这是百度的一道笔试题,考查对树这种基本数据结构以及递归函数的理解。
当访问到某一结点时,把该结点添加到路径上,并累加当前结点的值。如果当前结点为叶结点并且当前路径的和刚好等于输入的整数,则当前的路径符合要求,我们把它打印出来。如果当前结点不是叶结点,则继续访问它的子结点。当前结点访问结束后,递归函数将自动回到父结点。因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值,以确保返回父结点时路径刚好是根结点到父结点的路径。我们不难看出保存路径的数据结构实际上是一个栈结构,因为路径要与递归调用状态一致,而递归调用本质就是一个压栈和出栈的过程。
转载请注明原文地址:https://kaotiyun.com/show/nxmZ777K
0
程序员面试
相关试题推荐
TheUnitedStatesInterstateHighwaySystemisaninfrastructurefeatofunprecedentedproportions.Notonlydoesitjoinallfi
TheGreeksassumedthatthestructureoflanguagehadsomeconnectionwiththeprocessofthought,whichtookrootinEuropelon
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1,-2,3,10,-4,7,2,-5,和最大的子数组为3,10,
列举ADO.NET中的五个主要对象,并简单描述
列举一下你所了解的XML技术及其应用
数据库的优化设计?
触发器分为事前触发和事后触发,这两种触发有和区别。语句级触发和行级触发有何区别。
设置DOS窗口为“快速编辑模式”。
不能显示和编辑备注内容的视图模式是()A.普通视图B.大纲视图C.幻灯片视图D.备注页视图
下列不属于软件调试技术的是()。
随机试题
若电阻的真值是1000Ω,测量结果是1002Ω,则正确的结论是_________。
Thesharingeconomyhasbeenwidelyhailedasamajorgrowthsector,bysourcesrangingfromFortunemagazinetoPresidentO
金融期权是指其持有者能在规定的期限内按交易双方商定的价格购买或出售一定数量的某种金融工具的权利。()
关于公共物品的说法,正确的有()。
(2016·四川)微课教学时间短,教学内容少,只讲授一两个知识点。因此,微课不需要全面和系统的课程体系。()
近期你单位员工纪律涣散、工作效率不高,领导让你针对这种情况进行一次整改。你怎么做?
×××××××××(标题)各区县人民政府,市政府各委办局,市各直属单位:2003年,在市委、市政府领导下,全市上下以“三个代表”重要思想为指导,认真学习贯彻党的十六届三中全会和全国再就业工作座谈会精神,与时俱进,开拓创新,劳动和社会保障工作
这些像尘土一样卑微的人们,他们的身影出现在我的视线里,他们的精神沉淀在我的心灵里,他们常常让我感觉到这个平凡的世界是那么可爱,这个散淡的世界其实是那么默契,而看起来如草芥一样的生命种子,其实是那么坚韧和美丽。最符合这段文字中心思想的是()。
Whenyouthinkofmonkeys,youprobablythinkofthetropics.Fewspeciesofmonkeysventureintotemperatelands.Nevertheless,
Nowresearchersaredirectingmoreattentiontothesocialandculturalimpetusthatpropelleduniversitygraduatesintocareers
最新回复
(
0
)