【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