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

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

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

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

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

     比如输入整数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)


相关推荐

  • linux(11)配置环境变量「建议收藏」

    linux(11)配置环境变量「建议收藏」前言在自定义安装软件的时候,经常需要配置环境变量,下面进行详细解析&nbsp;环境变量配置文件|用户|配置文件||:|:||系统环境|/ect/profil

  • leetcode-41缺失的第一个正数

    leetcode-41缺失的第一个正数原题链接给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。进阶:你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗?示例 1:输入:nums = [1,2,0]输出:3示例 2:输入:nums = [3,4,-1,1]输出:2示例 3:输入:nums = [7,8,9,11,12]输出:1 提示:0 <= nums.length <= 300-231 <= nums[i] <= 231 – 1题解

  • Kubernetes从懵圈到熟练:读懂这一篇,集群节点不下线

    Kubernetes从懵圈到熟练:读懂这一篇,集群节点不下线Kubernetes从懵圈到熟练:读懂这一篇,集群节点不下线

  • c语言random函数在vc,C++ 中随机函数random函数的使用方法

    c语言random函数在vc,C++ 中随机函数random函数的使用方法C++中随机函数random函数的使用方法一、random函数不是ANSIC标准,不能在gcc,vc等编译器下编译通过。可改用C++下的rand函数来实现。1、C++标准函数库提供一随机数生成器rand,返回0-RAND_MAX之间均匀分布的伪随机整数。RAND_MAX必须至少为32767。rand()函数不接受参数,默认以1为种子(即起始值)。随机数生成器总是以相同的种子开始,所以形成…

  • 为什么当程序员?来听听漂亮国程序员的理由

    为什么当程序员?来听听漂亮国程序员的理由看看在国外当程序员的理由,与我们国内有什么不同!

  • sql中的联合查询「建议收藏」

    sql中的联合查询「建议收藏」我们在实际应用中,或许会用到关于sql的联合查询的应用,下面来总结一下联合查询的具体应用,做一下记录便于记忆。首先,通过一个实例来讲一下联合查询(关键词union)语法:select………unionselect……..union…….select*fromempoloyeeswhereemaillike”%a%”ordepartment_id>90;改用union的用法select*fromempol

发表回复

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

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