首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 则打印出两条路径:10, 12和10, 5, 7。 二元树结点的数据结构定义为: struct
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 则打印出两条路径:10, 12和10, 5, 7。 二元树结点的数据结构定义为: struct
admin
2019-03-29
155
问题
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
例如输入整数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
程序员面试
相关试题推荐
Notuntilthe1980’s______inBeijingstarttofindwaystopreservehistoricbuildingsfromdestruction.
"Thecatdoesnotofferservices,"WilliamBurroughswrote."Thecatoffersitself."Butitdoessowithunapologeticcontradict
Signslike"Pleaseratemefivestars"pointtoagrowingproblemwithbusinessesintheon-demandeconomyofapp-basedservices
求1+2+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句(A?B:C)。
输入n个整数,输出其中最小的k个。例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。
.概述三层结构体系
删除字符串中的数字并压缩字符串(神州数码以前笔试题),如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。(下面的算法只需要一次遍历,不需要开辟新空间,时间复杂度为O(N))
在Google搜索引擎中搜索多个关键词“office”,“WPS”。
将远程服务器中名为“通知”的文件在不下载的情况下进行编辑,修改201教室为303教室,然后直接保存,并在关闭编辑窗口后上传。
下列不属于软件调试技术的是()。
随机试题
微型计算机存储系统中的的Cache是
A.延髓B.脊髓C.脑桥D.下丘脑基本生命中枢位于
A.临时心脏起搏B.药物治疗C.安置永久性心房起搏器D.心脏电复律E.安置永久性房室顺序双腔心脏起搏器下列病例采用上述哪项治疗最合理:男性,26岁。因感冒2周后感胸闷就诊。体检:心率40~45次/min
4月28日,气温18~28.5℃,动物医院接诊一京巴犬(小名贝贝),1岁,♂,体况中等,体温39.3℃。主诉,最近发现该犬小便次数增加,颜色发黄,吃食渐少。临诊发现该犬精神委顿,不停弓腰举尾,但仅排出少量黄色尿液,滴水状,浑浊;腹胀,触诊腹壁较紧张、神态不
某档案馆大型档案储存室设计时整体采用二氧化碳气体管网灭火系统保护。档案储存室建筑面积790m2,地面至吊顶垂直距离4m,吊顶净高1m。则设计时应划分为()个气体灭火系统防护区。
会计核算软件具有查询机内会计数据的功能,发现错账时,可以随时修改。()
乙公司2014年全年税前会计利润为988万元,经查乙公司当年营业外支出中有12万元为税收滞纳金,适用所得税税率为25%。已知乙公司递延所得税负债年初数为40万元,年末数50万元,递延所得税资产年初数为25万元,年末数为20万元。乙公司2014年的所得税费用
"Whereistheuniversity?"isaquestionmanyvisitorstoCambridgeask,butnoonecangivethemaclearanswerforthereisno
MycousinNancyisofteninapoisonousmood;Isupposeit’sbecausesheis._____child.
A、Findanotherequipment.B、Connecthiscomputertotheoffice.C、Findthemanger’soffice.D、Dopreparationfortheminutes.B女
最新回复
(
0
)