首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 10
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 10
admin
2014-11-15
135
问题
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
例如输入整数22和如下二元树
10
/ \
5 12
/ \
4 7
则打印出两条路径: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/dDmZ777K
0
程序员面试
相关试题推荐
Theimmunesystemisequalincomplexitytothecombinedintricaciesofthebrainandnervoussystem.Thesuccessoftheimmune
YouaregoingtostudyabroadandshareanapartmentwithJohn,alocalstudent.Writehimane-mailtotellhimaboutyourli
删除串中指定的字符
概述.NET里对remoting和webservice两项技术的理解和实际中的应用。
什么是ASP.net中的用户控件
添加一个新的类型是计算机管理员的用户John
设置TCP/IP属性的首选DNS服务器地址202.112.80.106。
若按下Shift键同时用鼠标分别单击幻灯片中的标题、文本和图片对象,则()。A.仅最后单击的对象被选中B.三个对象被同时选中C.仅标题对象被选中D.仅图形对象被选中
以下关于输入法状态切换的组合键正确的是______A.使用Ctrl+、来切换中文标点和英文标点B.使用Ctrl+空格键来打开或关闭中文输入法C.使用Shift+空格键来切换半角输入模式和全角输入模式D.使用Shift+Ctrl来切换半角输入模式和
请在当前幻灯片中插入一个组织结构图,其中第一层与第二层之间有一个助手图框。
随机试题
服务质量最表层的内涵应包括服务的哪些要求()①安全性;②适用性;③有效性;④经济性;⑤可靠性。
令四面骑驰下,期山东为三处。期:山东:
患者男性,45岁,10年前患慢性丙型肝炎,近5年来出现乏力、腹胀,1个月前出现皮肤及巩膜黄染。无发热及皮肤瘙痒,无白便现象。查体:巩膜明显黄染,腹软,肝未触及,脾肋下2cm,质地韧无触痛,移动性浊音阳性。与该患者的黄疸不符的检查结果是
根据我国《进出口商品检验法》的规定,属于法定检验的商品即列入《商检机构实施检验的进出口商品种类表》(商品检验检疫目录)内的商品。
以下关于外汇市场及外汇产品的说法正确的是()。
分析各个对象在物流市场中所占的份额,并提出对应不同对象的战略和策略方案的分析方法,称为时间结构分析。()
张老师在班主任例会上谈到现在的学生难管理时说:“当学生违反纪律时,我对他们大声地严厉批评,但是他们却越来越不像话”。对学生不良行为的增加,可以用行为主义的()观点来解释。
甲贩运走私货物,驾车路过某检查站时,为了避免被发现,遂强行闯关,检查人员乙上前示意停车接受检查,甲不予理睬,加大油门冲向关卡,乙没有及时躲避而被撞倒,导致头部着地身亡。甲对乙的死亡的心理态度属于()。
结合材料回答问题:材料1我国著名的历史学家胡绳先生的著作《中国共产党七十年》,他在这部著作中对辛亥革命有这样中肯的评价:“中华民国的成立并没有给人们带来预期的民族独立、民主和社会进步”……“如果脱离中国近现代革命史的全过程来看,也许会把
设xn=xn.
最新回复
(
0
)