【C/C++练习题】二叉树中和为某一值的路径

《剑指Offer》面试题34：二叉树中和为某一值的路径

1 题目

输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径

2 分析

本题目的是找出所有符合条件的路径，因此要遍历二叉树，使用先序遍历可以从根节点开始。

需要一个辅助空间存储遍历过的树节点。当程序遍历到叶子节点的时候，如果满足所有路径和为指定值，打印路径。

在递归遍历节点过程中，当程序遍历完一条完整的路径，需要退回上一级父节点，此时也在路径中删除当前节点。

3 代码

  

   

    

     

    
    

     

      /*
     
    
   

    

     

    
    

     

      *********************************************************************************************************
     
    
   

    

     

    
    

     

      *
     
    
   

    

     

    
    

     

      * 模块名称 : 主程序
     
    
   

    

     

    
    

     

      * 文件名称 : demo.cpp
     
    
   

    

     

    
    

     

      * 版 本 : V1.0
     
    
   

    

     

    
    

     

      * 说 明 : 《剑指Offer》笔试题，二叉树和为某一值得路径
     
    
   

    

     

    
    

     

      *
     
    
   

    

     

    
    

     

      * 修改记录 :
     
    
   

    

     

    
    

     

      * 版本号 日期 作者 说明
     
    
   

    

     

    
    

     

      * V1.0 2019-08-13 hinzer 正式发布
     
    
   

    

     

    
    

     

      *
     
    
   

    

     

    
    

     

      * 码云链接：
     
    
   

    

     

    
    

     

      *
     
    
   

    

     

    
    

     

      *********************************************************************************************************
     
    
   

    

     

    
    

     

      */
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #include "iostream"
     
    
   

    

     

    
    

     

      #include "cstdlib"
     
    
   

    

     

    
    

     

      #include <vector>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct Node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int m_nValue;
     
    
   

    

     

    
    

     

      	Node* m_pLeft;
     
    
   

    

     

    
    

     

      	Node* m_pRight;
     
    
   

    

     

    
    

     

      }BinaryTreeNode;	
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void FindPath(BinaryTreeNode* pNode, int expectedSum);
     
    
   

    

     

    
    

     

      void FindPath(BinaryTreeNode* pNode, vector<int> &path , int expectedSum);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      /******************************************************************************
     
    
   

    

     

    
    

     

      * 函数介绍：确定二叉树和为某一值得路径
     
    
   

    

     

    
    

     

      * 输入参数：pNode二叉树头节点指针, expectedSum期望路径和
     
    
   

    

     

    
    

     

      * 输出参数：无
     
    
   

    

     

    
    

     

      * 返回值：无
     
    
   

    

     

    
    

     

      * 备注：无
     
    
   

    

     

    
    

     

      ******************************************************************************/
     
    
   

    

     

    
    

     

      void FindPath(BinaryTreeNode* pNode, int expectedSum)
     
    
   

    

     

    
    

     

      {	
     
    
   

    

     

    
    

     
	if (NULL == pNode)
     
    
   

    

     

    
    

     
		return ;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	vector<int> path;
     
    
   

    

     

    
    

     
	FindPath(pNode, path, expectedSum);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      /******************************************************************************
     
    
   

    

     

    
    

     

      * 函数介绍：确定二叉树和为某一值得路径
     
    
   

    

     

    
    

     

      * 输入参数：pNode二叉树头节点指针, path存储路径, expectedSum期望路径和
     
    
   

    

     

    
    

     

      * 输出参数：无
     
    
   

    

     

    
    

     

      * 返回值：无
     
    
   

    

     

    
    

     

      * 备注：无
     
    
   

    

     

    
    

     

      ******************************************************************************/
     
    
   

    

     

    
    

     

      void FindPath(BinaryTreeNode* pNode, vector<int> &path , int expectedSum)
     
    
   

    

     

    
    

     

      {	
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	path.push_back(pNode->m_nValue);	//插入节点数值
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//1.回归条件--确定为叶子节点
     
    
   

    

     

    
    

     
	if ((NULL == pNode->m_pLeft) && (NULL == pNode->m_pRight))
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if (pNode->m_nValue == expectedSum)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			cout << "a path is found:";
     
    
   

    

     

    
    

     

      			vector<int>::iterator iter = path.begin();
     
    
   

    

     

    
    

     
			for(;iter != path.end();++iter)
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     

      				cout << *iter << "-";
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      			cout << endl;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//2.不是叶子节点，对子节点进行递归调用
     
    
   

    

     

    
    

     
	if (NULL != pNode->m_pLeft)
     
    
   

    

     

    
    

     
		FindPath(pNode->m_pLeft, path, expectedSum - pNode->m_nValue);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	if (NULL != pNode->m_pRight)
     
    
   

    

     

    
    

     
		FindPath(pNode->m_pRight, path, expectedSum - pNode->m_nValue);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	path.pop_back();	//退回父节点，在路径上要三处当前节点
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      /******************************************************************************
     
    
   

    

     

    
    

     

      * 函数介绍：功能测试函数
     
    
   

    

     

    
    

     

      * 输入参数：无
     
    
   

    

     

    
    

     

      * 输出参数：无
     
    
   

    

     

    
    

     

      * 返回值：无
     
    
   

    

     

    
    

     

      * 备注：无
     
    
   

    

     

    
    

     

      ******************************************************************************/
     
    
   

    

     

    
    

     

      void test01()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      // 8(node1)
     
    
   

    

     

    
    

     

      // 6(node2) 10(node3)
     
    
   

    

     

    
    

     

      // 5(node4) 13(node5) 9(node6) 11(node7)
     
    
   

    

     

    
    

     

      	BinaryTreeNode* node1  = new BinaryTreeNode();
     
    
   

    

     

    
    

     

      	BinaryTreeNode* node2  = new BinaryTreeNode();
     
    
   

    

     

    
    

     

      	BinaryTreeNode* node3  = new BinaryTreeNode();
     
    
   

    

     

    
    

     

      	BinaryTreeNode* node4  = new BinaryTreeNode();
     
    
   

    

     

    
    

     

      	BinaryTreeNode* node5  = new BinaryTreeNode();
     
    
   

    

     

    
    

     

      	BinaryTreeNode* node6  = new BinaryTreeNode();
     
    
   

    

     

    
    

     

      	BinaryTreeNode* node7  = new BinaryTreeNode();
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//node1
     
    
   

    

     

    
    

     

      	node1->m_nValue = 8;
     
    
   

    

     

    
    

     

      	node1->m_pLeft = node2;
     
    
   

    

     

    
    

     

      	node1->m_pRight = node3;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//node2
     
    
   

    

     

    
    

     

      	node2->m_nValue = 6;
     
    
   

    

     

    
    

     

      	node2->m_pLeft = node4;
     
    
   

    

     

    
    

     

      	node2->m_pRight = node5;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//node3
     
    
   

    

     

    
    

     

      	node3->m_nValue = 10;
     
    
   

    

     

    
    

     

      	node3->m_pLeft = node6;
     
    
   

    

     

    
    

     

      	node3->m_pRight = node7;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//node4
     
    
   

    

     

    
    

     

      	node4->m_nValue = 5;
     
    
   

    

     

    
    

     

      	node4->m_pLeft = nullptr;
     
    
   

    

     

    
    

     

      	node4->m_pRight = nullptr;	
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//node5
     
    
   

    

     

    
    

     

      	node5->m_nValue = 13;
     
    
   

    

     

    
    

     

      	node5->m_pLeft = nullptr;
     
    
   

    

     

    
    

     

      	node5->m_pRight = nullptr;	
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//node6
     
    
   

    

     

    
    

     

      	node6->m_nValue = 9;
     
    
   

    

     

    
    

     

      	node6->m_pLeft = nullptr;
     
    
   

    

     

    
    

     

      	node6->m_pRight = nullptr;	
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//node7
     
    
   

    

     

    
    

     

      	node7->m_nValue = 11;
     
    
   

    

     

    
    

     

      	node7->m_pLeft = nullptr;
     
    
   

    

     

    
    

     

      	node7->m_pRight = nullptr;	
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//测试部分
     
    
   

    

     

    
    

     
	FindPath(node1, 27);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	delete node1;delete node2;
     
    
   

    

     

    
    

     
	delete node3;delete node4;
     
    
   

    

     

    
    

     
	delete node5;delete node6;
     
    
   

    

     

    
    

     
	delete node7;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(int argc, char const *argv[])
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	test01();
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行结果

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/99544525