首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 10
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 10
admin
2014-11-15
128
问题
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
例如输入整数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
程序员面试
相关试题推荐
TheGreeksassumedthatthestructureoflanguagehadsomeconnectionwiththeprocessofthought,whichtookrootinEuropelon
Signslike"Pleaseratemefivestars"pointtoagrowingproblemwithbusinessesintheon-demandeconomyofapp-basedservices
.概述三层结构体系
输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。例如输入12,从1到12这些整数中包含1的数字有1,10,11和12,1一共出现了5次。
触发器分为事前触发和事后触发,这两种触发有和区别。语句级触发和行级触发有何区别。
在邮件中设置图片背景。
设置TCP/IP属性的备用DNS服务器地址202.112.88.31。
Dreamweaver的视图(View)菜单中,Grid→settings表示______。A.选择计量系统来设定标尺单位B.显示一个应用当前设置的背景网格C.使插入对象与最近的对齐设置对齐D.进行网格设置
将E-R图转换到关系模式时,实体与联系都可以表示成______。
IPSAN区别于FCSAN以及IBSAN的主要技术是采用__________实现异地间的数据交换。
随机试题
A、Humanbeingsaretheonlyanimalswhocanlaugh.B、Onestartslaughingwhenheisaboutsixmonthsold.C、Laughterhasmanyfu
为了区分全塑市话通信电缆的端别,一般规定B端用()色标志。
下列哪几项七情配伍关系是临床应当避免配伍的()
男,25岁,股骨颈骨折金属物内固定后复查,了解骨折对立、对线情况,最佳节方法是:
气虚型月经量多的临床表现是血热型月经量多的临床表现是
关于聚众斗殴罪的主体,下列哪一说法是正确的?()
证券停牌时,证券交易所发布的行情中包括该证券的信息;证券停牌后,行情信息中仍应包含该证券的信息。()
下列各项中,应计入制造企业存货成本的有()。
大学退学的人越来越多,据最新统计,退学率有3%,很多人退学去创业,认为自己能成为比尔.盖茨或者乔布斯。你怎么看?
在通胀预期的大背景下,黄金作为硬通货,更有利于保存和增值,因而得到了更多人的_______。但真正的利润获得者只有少数,当多数人都发现了某一市场的利润空间,正_______着这是获利者清盘了结盈利的最佳时间点。填入划横线部分最恰当的一项是:
最新回复
(
0
)