首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 10
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 10
admin
2014-11-15
136
问题
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
例如输入整数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
程序员面试
相关试题推荐
Writealettertothedirectorofthelibraryinyouruniversity,givingsomeadviceonhowtoimprovethelibraryservice.You
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:因此返回true。如果输入7、4、6、5,没有哪棵树的后序遍历
2005年11月金山笔试题。编码完成下面的处理函数。函数将字符串中的字符’*’移到串的前部分,前面的非’*’字符后移,但不能改变非’*’字符的先后顺序,函数返回串中字符’*’的数量。如原始串为:ab**cd**e*12,处理后为*****abcde12,函
触发器分为事前触发和事后触发,这两种触发有和区别。语句级触发和行级触发有何区别。
如果利用局域网连接Internt,在Internet选项中进行设置代理服务器HTTP:proxy.pku.edu.cn端口:8080。
在当前窗口界面中,根据“添加打印机”向导,安装网络打印机,输入名称为“\\192.168.18.18\MicrosoftXPSDocumentWriter”。
将远程服务器中名为“通知”的文件在不下载的情况下进行编辑,修改201教室为303教室,然后直接保存,并在关闭编辑窗口后上传。
请在MSN共享文件会话界面上,利用工具栏添加共享文件,文件位置为“我的文档\注册.txt”。
将桌面背景设置为图片WindowsXP。
下列叙述正确的是______A.通过“我的电脑”图标可以浏览和使用所有的计算机资源B.“我的电脑”是一个文件夹C.“回收站”用于存放被删除的对象,置入“回收站”中的对象在关机后自动消失D.用户可以在桌面上创建文件夹或快捷方式
随机试题
横道图不适用于()。
食管胃底静脉曲张破裂大出血患者,既往有冠心病史,以下处理哪项是正确的
第一批公布的我国国家非处方药规定全部按
韩愈,字退之,昌黎人。父仲卿,无名位。愈生三岁而孤,养于从父兄。愈自以孤子,幼刻苦学儒,不俟奖励。……洎举进士,投文于公卿间,故相郑余庆颇为之延誉,由是知名于时。寻登进士第。宰相董晋出镇大梁,辟为巡官。府除,徐州张建封又请为其宾佐。愈发言真率,无
公安机关的宗旨是全心全意为人民服务。()
2
可在Global.asa文件中用______标记为应用程序声明类型库。
对于长度为n的顺序存储的线性表,当随机插入和删除一个元素时,需平均移动元素的个数为【】。
A、Becausehedied5000yearsagointhemountain.B、Becausescientistsfoundanarrowheadunderhisshoulder.C、Becausehewask
It’sofficialthatmarriedpeoplearehealthier,oratleasttheythinktheyare.AnAmerican【B1】______ofover100,000peoplesh
最新回复
(
0
)