首页 > 代码库 > 4.在二元树中找出和为某一值的所有路径
4.在二元树中找出和为某一值的所有路径
http://zhedahht.blog.163.com/blog/static/254111742007228357325/
http://www.cnblogs.com/qi09/archive/2011/05/24/2055643.html
题目:输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
例如输入整数22和如下二元树
10
/ \
5 12
/ \
4 7
则打印出两条路径:10, 12和10, 5, 7。
思路:
1、当访问到某一节点时,把该结点的值添加到当前和变量,且把该结点压入栈中。
2、若结点为叶子结点,且当前和变量==期望的和,则打印栈中的结点值,即为所需的路径。
3、若结点不是叶子结点,继续访问它的左孩子结点,访问它的右孩子结点。
4、删除该结点。包括从当前和变量中减去结点值,从栈中弹出结点值。此时,已回到父结点。
程序中的栈,利用STL中的vector,这样简化了编码工作。
/////////////////////////////////////////////////////////////////////// // 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(); } void FindPath( BinaryTreeNode* pTreeNode, // a node of binary tree int expectedSum // the expected sum ) { int curSum = 0; std::vector<int> path; FindPath(pTreeNode,expectedSum,path,curSum); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。