首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 则打印出两条路径:10, 12和10, 5, 7。 二元树结点的数据结构定义为: struct
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 则打印出两条路径:10, 12和10, 5, 7。 二元树结点的数据结构定义为: struct
admin
2019-03-29
73
问题
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
例如输入整数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
2005年11月15日华为软件研发笔试题。实现一单链表的逆转。
四个工人,四个任务,每个人做不同的任务需要的时间不同,求任务分配的最优方案。(2005年5月29日全国计算机软件资格水平考试——软件设计师的算法题)。
存储过程和函数的区别
在金山毒霸2008中,阻止下载运行.ActiveX控件。
当密码为123456时,请撤消对工作簿Book1的密码及结构保护设置。
请对工作簿Book1的结构和窗口设置保护,使工作簿和工作表不能进行移动和隐藏等操作。
将E-R图转换到关系模式时,实体与联系都可以表示成______。
任何一个团队从开始组建到最终达到绩效要求,需要一个周期。依据塔克曼群体发展模型,结合IT服务管理工作特性,将团队建设周期分为四个阶段,它们分别是(未按正确次序排列):①风暴期②表现期③组建期④规范期团队建设周期的正确排序为______。
IT服务风险管理中,风险的监控是指跟踪已识别的危险,检测残余风险和识别新的风险,保证风险计划的执行,并评价这些计划对减轻风险的有效性。风险监控是整个生命周期中一个持续进行的过程。下面______不是风险监控的基本方法。
随机试题
诊断感染性心内膜炎最具特征性的表现是
在FIDIC施工合同条件中,预付款担保应采用()提供的保函。
根据《建设项目工程结算编审规程》,工程价款结算主要包括()。
下列关于举证时限的说法,错误的是()。
试验管理标准与制度主要包括()。
云南大理蝴蝶泉是著名的()。
急性心肌梗死时最早、最突出的症状是()。
研究显示,相比于农村地区,城市地区居民哮喘、湿疹、过敏性鼻炎和结膜炎等疾病患病率不断攀升。有个假设是乡村生活环境中的某些因素,譬如自小接触到特定细菌能让人免受某些变应原的危害,或是城市地区的许多污染物诱发了这些过敏症的发展。对这段文字理解正确的一项是:
1995年6月,A市某食品公司经理刘某委托去B市办事的某个商行负责人张某将该公司的营业执照副本和盖有该公司合同专用章的空白合同书交给公司驻B市办事处的王某。张某到B市后,因事务缠身一直未将营业执照副本和空白合同书交到王某的手中。同年7月2日,张某从朋友处得
下列行为中,构成包庇罪的有()。
最新回复
(
0
)