首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 10
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 10
admin
2014-11-15
138
问题
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
例如输入整数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
程序员面试
相关试题推荐
TruthinadvertisingisaconceptcentraltotheAmericanfreemarketeconomicsystem.Accordingtothistheory,companiesthat
It’swellknownthatbeingbilingualhascognitivebenefits:switchingbetweentwolanguageshasbeencomparedtomentalgymnast
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
删除串中指定的字符
2005年11月23日慧通笔试题:写一函数判断某个整数是否为回文数,如12321为回文数。可以用判断入栈和出栈是否相同来实现(略微复杂些),这里是将整数逆序后形成另一整数,判断两个整数是否相等来实现的。
列举一下你所了解的XML技术及其应用
从当前界面上开始操作,把联机用户min邀请加入到对话框中,开始多用户对话。
以下关于输入法状态切换的组合键正确的是______A.使用Ctrl+、来切换中文标点和英文标点B.使用Ctrl+空格键来打开或关闭中文输入法C.使用Shift+空格键来切换半角输入模式和全角输入模式D.使用Shift+Ctrl来切换半角输入模式和
在PPoint中,被选中对象虚框上的8个小方框称为()。A.尺寸控制点B.文本插入点C.有效区域范围D.选中对象标记
请在当前幻灯片中插入一个组织结构图,其中第一层与第二层之间有一个助手图框。
随机试题
给一位左上肢骨折病人床上擦浴,下述何项正确
依据《道路交通安全法》的规定,对有证据证明交通事故中非机动车驾驶人、行人违反道路交通安全法律、法规,机动车驾驶人已经采取必要处置措施的情形,关于双方责任的承担,下列说法中,正确的是()。
在万能寿险中,保单持有人要求提高保险金额的前提条件是()。
读下面经纬网图,回答下列问题。若此时国际标准时间为3月21日8时,则下列叙述正确的是()。①甲地处于昼半球范围内②乙地的区时为3月20日23时③丙地与甲地分属于两个不同的日期④丁地的地方时是11时20分
幼儿园体育的重要目标是()。
中学语文教学结果性目标可使用的行为动词是()
右图展示了1992年我国农村生活能源构成。读图完成下列问题:(1)简述当时我国农村生活能源构成的突出特点:_______。(2)根据右图并结合地区农业生产及环境特点,可以推测,长江中下游平原农村的生活能源以_______为主,东南丘陵
某书店准备向出版社订购一批本地旅游新版书,书的定价为每本30元,订购价为每本15元。如果该书在年底前尚未售出,则不得不以每本5元的价格退回给出版社。根据以往经验,按定价售出150本、160本、170本、180本的概率分别为0.1、0.2、0.4、0-3。为
一台Cisco6500交换机的生成树优先级是20480,若将其优先级提升2级,正确的配置命令是()。
Whenmenandwomengettogether,thereare,ineffect,twoworlds--hisandhers.Theyhavedifferentvalues,【B1】______,andhab
最新回复
(
0
)