二叉树中和为某一值的路径

二叉树中和为某一值的路径

题目:

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

二义树结点的定义如下:

struct BinaryTreeNode{
 int m_nValue;
 BinaryTreeNode *m_pLeft;
 BinaryTreeNode *m_pRight;
};

思路：

由于路径是从根结点出发到叶结点，也就是说路径总是以根结点为起始点，因此我们首先需要遍历根结点。在树的前序、中序、后序三种遍历方式中，只有前序遍历是首先访问根结点的。

当用前序遍历的方式访问到某一结点时，我们把该结点添加到路径上，并累加该结点的值。如果该结点为叶结点并且路径中结点值的和刚好等于输入的整数，则当前的路径符合要求，我们把它打印出来。如果当前结点不是叶结点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回到它的父结点。因此在函数退出之前要在路径上删除当前结点并减去当前结点的值，以确保返回父结点时路径刚好是从根结点到父结点的路径。

void FindPath(BinaryTreeNode *pRoot, int nSum)
{
 if (pRoot==NULL)
    return;
 vector<int> path;
 int nCurrentSum=0;
}
void FindPath(BinaryTreeNode *pRoot, int nSum, vector<int> &path, int &nCurrentSum)
{
 nCurrentSum+=pRoot->m_nValue;
 path.push_back(pRoot->m_nValue);

 //判断是否是叶结点
 bool isLeaf=pRoot->m_pLeft==NULL&&pRoot->m_pRight==NULL;
 //是叶结点且路径上的值等于设定值则打印路径
 if (isLeaf&&nCurrentSum==nSum)
 {
  vector<int>::iterator iter;
  for (iter=path.begin();iter!=path.end(); iter++)
  {
   printf("%d\t",*iter);
  }
  printf("\n");
 }
 //如果不是叶子结点，则遍历它的子结点
 if(pRoot->m_pLeft!=NULL)
 {
  FindPath(pRoot->m_pLeft,nSum,path,nCurrentSum);
 }
 if (pRoot->m_pRight!=NULL)
 {
  FindPath(pRoot->m_pRight,nSum,path,nCurrentSum);
 }
 //在返回父结点之前，在路径上删除当前结点,并且在当前和中删掉当前结点值
 nCurrentSum-=pRoot->m_nValue;
 path.pop_back();
}

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在JAVA中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

二叉树先序中序非递归算法

轻松搞定面试中的二叉树题目

本文永久更新链接地址：