二元树中和为某一值的全部路径

二元树中和为某一值的全部路径

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

             近期在这里看到一道面试题,看了题目和作者的解答后,感觉真是强大。

     题目:输入一个整数和一棵二元树。从树的根结点開始往下訪问一直到叶结点所经过的全部结点形成一条路径。打印出和与输入整数相等的全部路径。

     比如输入整数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<int>& path,         // a path from 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<int>::iterator iter = path.begin();           for(; iter != path.end(); ++ iter)                 std::cout << *iter << '\t';           std::cout << std::endl;      }      // if the node is not a leaf, goto its children      if(pTreeNode->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;      path.pop_back();} 

      细致看代码,你会发现,这样的方法遍历了解空间树,全部的叶子节点都会訪问到,

        假设二叉树是这种呢:

        二元树中和为某一值的全部路径

       依照这样的方法,20的两个孩子都会訪问到,可是,这在做无用功,由于,题目要求的是从根节点到叶子节点的路径和为22,当訪问到20的时候,路径和已是30了(大于22),再訪问20的孩子,路径和也会大于22,这样就没有必要再訪问20的孩子了。

       所以,应该避免这样的无效搜索,在遍历每一个节点的时候,先推断路径和是否大于目标值,假设大于的话,则不要遍历该节点的孩子,而且回溯。

      优化后的代码为:

void FindPath(	 BinaryTreeNode* pTreeNode, // a node of binary tree	 int expectedSum, // the expected sum	 std::vector<int>& path, // a path from root to current node	 int& currentSum // the sum of path	 ){	if(!pTreeNode)		return;	currentSum += pTreeNode->m_nValue;	if(currentSum > expectedSum){  //推断路径和是否会超出目标值,超出则回溯		currentSum -= pTreeNode->m_nValue;		return;	}	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<int>::iterator iter = path.begin();		for(; iter != path.end(); ++ iter)		std::cout << *iter << '\t';		std::cout << std::endl;	}	// if the node is not a leaf, goto its children	if(pTreeNode->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;	path.pop_back();}

        在原来的代码里添加�了例如以下代码:

if(currentSum > expectedSum){  //推断路径和是否会超出目标值,超出则回溯		currentSum -= pTreeNode->m_nValue;		return;	}

        剪去无效的子树,避免无效搜素,提高效率。

參考:

http://zhedahht.blog.163.com/blog/static/254111742007228357325/

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118895.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • CentOS7在线安装gcc及使用

    CentOS7在线安装gcc及使用CentOS7在线安装gcc及使用一.在线安装gcc(需要配置网络)在虚拟机VMwareWorkstation安装CentOS7后,系统是没有gcc的。进入系统根目录[root@localhost~],输入命令:[root@localhost~]yum-yinstallgccgcc-c++autoconfmake就会自动进行在线安装。完成后输入命令:[root…

  • qcustomplot 性能_cpu性能提升工具

    qcustomplot 性能_cpu性能提升工具Plot性能提升QCustomPlot采用了大量的技术比如自适应采样和文本对象缓存为了减少replot的时间。然而一些特性比如半透明的填充,反锯齿和粗线条都可能导致低效率。如果你在你的程序中注意到了这些。这有一些提示关于如何跳高Replot的性能。大部分时间耗费在绘图函数上尤其是绘制高密度的图形和其他图。为了最大性能思考下面几点:使用Qt4.8.0及以上的版本,性能将会有双倍或

  • NAT的双机热备方案

    一般的NAT组网中,内网用户通过单台设备进行NAT转换访问外网,NAT设备承担了所有内外网之间的流量,无法规避单点故障。一旦发生单点故障,将导致内网用户无法与外网通信。随着用户对网络可靠性的要求越来越高,发生单点故障导致网络间断是不可接受的。因此在重要节点处一般都部署两台或者多台设备,构成冗余备份组网,但如果设备之间不能实时的进行数据备份的话,链路切换时还是会导致用户的业务中断。双机热备方案可…

  • wget(1.11.4) for win「建议收藏」

    wget(1.11.4) for win「建议收藏」下载wget(1.11.4)forwin安装添加wget环境变量,这样使用就更方便了,右键计算机->属性->高级系统设置->高级->环境变量->选中PATH->编辑,在最后添加;C:\ProgramFiles(x86)\GnuWin32\bin下载文件wget网址而要让档案自动储存到指令的目录下,则需要借用-P这个参数,可以使用以下的指令wge…

  • css flex布局实现文字垂直居中

    css flex布局实现文字垂直居中<style>.innner{display:flex;background-color:#ea4d22;height:100px;/*line-height:100px;*//*text-align:center;*/justify-content:center;flex-direction:column;}.i.

  • TextMate已激活成功教程

    TextMate已激活成功教程在pcbeta的帖子里找到了这个传说中的MAC杀手级武器的激活成功教程,针对的是1.5.8版本,摘抄如下:这个号称TheMissingEditorforMacOSX的编辑器我就不介绍了,我就说说如何注册吧。第一种方法:花39欧元第二种方法:UninstallfirstandInstalagain,justopentheTextMateunix(Apps

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号