二元树中和为某一值的所有路径（递归与非递归的方法）

迈不过友情╰ 2023-08-17 15:42 83阅读 0赞

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

例如输入整数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<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
           path.pop_back();
    }

非递归的方法

在使用非递归的方法的时候要注意，我在这里使用的是后序遍历，因为只有后续遍历才会把父节点保存到最后，而父节点是路径中非常重要的节点，不能随便删除。后续遍历到叶子节点时就可以做一个判断，如果该节点是叶子节点并且总和与给定的相同，即输出。这时候路径正好保存在我们的栈中。

#include "stdafx.h"
    #include <iostream>
    #include <vector>
    using namespace std;
    
    typedef struct BinTreeNode{
    	char data;
    	BinTreeNode *lChild;
    	BinTreeNode *rChild;
    }*BiTree;
    
    //创建一个二叉树
    void createBinTree( BiTree &T, const string &str, int *index )
    {
    	if ( *index < str.size() )
    	{
    		char tmpChar = str[(*index)++];
    		if ( tmpChar  == '#' )    T = NULL;
    		else {
    			if (!( T = new BinTreeNode ) ) throw runtime_error("error!");
    			T->data = tmpChar;
    			createBinTree(T->lChild, str, index );
    			createBinTree(T -> rChild, str, index );
    			
    		}
    	}
    }
    
    
    void FindPath( BinTreeNode *pRoot, int expectedSum )
    {
    	if ( pRoot == NULL )
    		return;
    	vector<BinTreeNode *> vTree;
    	BinTreeNode *pTemp = pRoot;
    	BinTreeNode *isViseted = NULL;
    	int currentSum = 0;
    
    	while ( pTemp || !vTree.empty())
    	{
    		if ( pTemp != NULL )
    		{
    			vTree.push_back( pTemp );
    			currentSum += pTemp->data;
    			pTemp = pTemp ->lChild;
    		}
    		else
    		{
    			pTemp = vTree.back();
    			if ( pTemp -> rChild == NULL || pTemp ->rChild == isViseted )
    			{
    				//找到了符合条件的叶子节点
    				if ( pTemp -> lChild == NULL && 
    					pTemp -> rChild == NULL &&
    					currentSum == expectedSum )
    				{
    					for (int i = 0; i < vTree.size(); ++i)
    						cout<<vTree[i]->data<<' ';
    					cout<<endl;
    				}
    
    				isViseted = pTemp;
    				currentSum -= pTemp->data;
    				pTemp = NULL;
    				vTree.pop_back();
    
    			}
    			else
    				pTemp = pTemp -> rChild;
    		}
    	}
    
    }
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	string str="AB#D##C##";    //测试树  
    	int index=0;  
    	BinTreeNode *T;  
    	createBinTree(T,str,&index);  
    
    	int sum = 'A' + 'B' + 'D';
    	FindPath(T,sum);
    	return 0;
    }

参考文献：

[http://zhedahht.blog.163.com/blog/static/254111742007228357325/][http_zhedahht.blog.163.com_blog_static_254111742007228357325]

[http_zhedahht.blog.163.com_blog_static_254111742007228357325]: http://zhedahht.blog.163.com/blog/static/254111742007228357325/