首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 则打印出两条路径:10, 12和10, 5, 7。 二元树结点的数据结构定义为: struct
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 则打印出两条路径:10, 12和10, 5, 7。 二元树结点的数据结构定义为: struct
admin
2019-03-29
130
问题
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
例如输入整数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
程序员面试
相关试题推荐
TheGreeksassumedthatthestructureoflanguagehadsomeconnectionwiththeprocessofthought,whichtookrootinEuropelon
RememberNapsterorGrokster?Bothservicesalloweduserstosharecomputerfiles—usuallydigitalmusic—thatinfringedthecopyr
[A]Updateyourbudget[B]Submitachangeofaddressform[C]Bookacleaningservicebeforehand[D]Scheduleawalk-t
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少总跳法,并分析算法的时间复杂度。
设置发送邮件服务器的帐户名bob1和密码20022002。
如果利用局域网连接Internt,在Internet选项中进行设置代理服务器HTTP:proxy.pku.edu.cn端口:8080。
请在当前幻灯片中的图形前添加一个形状,并输入“技术部”。
随机试题
简述旅游中间商的管理措施
磺酰脲类药物的体内过程特点:
控制小儿风湿热复发首选的药物是
髋关节后脱位的典型体征是
对公司所在的区位进行分析,包括()。
在企业战略实施中,十分重视运用组织结构、激励手段和控制系统来促进战略实施的模式是()。
下列句子中没有语病的一项是()。
Advancingagemeanslosingyourhair,yourwaistlineandyourmemory,right?DanaDenisisjust40yearsold,but(21)______
雄孔雀漂亮的羽毛主要是吸引雌孔雀的,但没人知道为什么这身漂亮的羽毛能在求偶中具有竞争的优势。一种解释是雌孔雀更愿意与拥有漂亮羽毛的雄孔雀为偶。以下哪项陈述准确描述了上文推论中的错误?
设f(x)在[a,b]上有定义,M>0且对任意的x,y∈[a,b],有|f(x)-f(y)|≤M|x-y|k.证明:当k>0时,f(x)在[a,b]上连续;
最新回复
(
0
)