首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 10
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 10
admin
2014-11-15
124
问题
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
例如输入整数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
程序员面试
相关试题推荐
Thecommitteehasanticipatedtheproblemsthat______intheroadconstructionproject.
Theimmunesystemisequalincomplexitytothecombinedintricaciesofthebrainandnervoussystem.Thesuccessoftheimmune
Signslike"Pleaseratemefivestars"pointtoagrowingproblemwithbusinessesintheon-demandeconomyofapp-basedservices
输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见,标点符号和普通字母一样处理。例如输入“Iamastudent.”,则输出“student.aamI”。
输入一个整数,求该整数的二进制表达中有多少个1。例如输入10,由于其二进制表示为1010,有两个1,因此输出2。
什么是ASP.net中的用户控件
将桌面背景设置为图片WindowsXP。
下列叙述正确的是______A.通过“我的电脑”图标可以浏览和使用所有的计算机资源B.“我的电脑”是一个文件夹C.“回收站”用于存放被删除的对象,置入“回收站”中的对象在关机后自动消失D.用户可以在桌面上创建文件夹或快捷方式
在幻灯片播放过程中,单击一次鼠标左键会()。A.切换到第一张幻灯片B.切换到最后一张幻灯片C.切换到上一张幻灯片D.切换到下一张幻灯片或本张幻灯片的下一个播放对象
请打开“计算器”应用程序,利用科学型模式将十进制的1234转换为十六进制。
随机试题
“文艺复兴三杰”是指
下列有关遗传密码的叙述,正确的是
关于CT透视的描述,错误的是
女,52岁。2个月来咳嗽,偶见痰中带血,首先应做的检查是
门脉性肝硬化形成的肝脏假小叶的病理特点不包括()。
按照土地使用权出让方式的不同,可以将土地使用权出让的成交价格分为()。
宣告一次审核结束的标志是()。
在旅游中期阶段,旅游者通常表现出()
小张和小李二人在400米标准环形跑道起点处,同向分别以120米/分钟、40米/分钟的速度同时出发,小张每追上小李一次,小张的速度减少10米/分钟,小李的速度增加10米/分钟,当二人速度相等时,则他们需要的时间是()。
国内某公司4月份在法国竞标一个项目,须在6月才能够确定是否中标,但公司没有把握能够竞争到该项目。该公司同时担忧,一旦中标之后须先支付30万欧元,而在当年1~4月份,外汇市场欧元/美元汇率走势并不稳定,波动范围在1.2500~1.4500之间。在此情况下,以
最新回复
(
0
)