在二元树中找出和为某一值的所有路径

本文主要是介绍在二元树中找出和为某一值的所有路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

路径。打印出和与输入整数相等的所有路径。

当访问到某一结点时，把该结点添加到路径上，并累加当前结点的值。如果当前结点为叶结点并且当前路
径的和刚好等于输入的整数，则当前的路径符合要求，我们把它打印出来。如果当前结点不是叶结点，则
继续访问它的子结点。当前结点访问结束后，递归函数将自动回到父结点。因此我们在函数退出之前要在
路径上删除当前结点并减去当前结点的值，以确保返回父结点时路径刚好是根结点到父结点的路径。我们
不难看出保存路径的数据结构实际上是一个栈结构，因为路径要与递归调用状态一致，而递归调用本质就
是一个压栈和出栈的过程。

#include<iostream>
#include<vector>using namespace std;//节点数据结构定义struct BinaryTreeNode
{int m_nValue;BinaryTreeNode *m_pLeft;BinaryTreeNode *m_pRight;
};void FindPath(BinaryTreeNode *pTreeNode, int expectedSum, vector<int> &path, int currentSum)
{if(!pTreeNode)return;currentSum += pTreeNode->m_nValue;path.push_back(pTreeNode->m_nValue);// 判断该节点是否为叶子节点bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight);if(currentSum == expectedSum && isLeaf){vector<int>::iterator iter = path.begin();for(; iter != path.end(); iter++)cout<<*iter<<' ';cout<<endl;}if(pTreeNode->m_pLeft)FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);if(pTreeNode->m_pRight)FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum);currentSum -= pTreeNode->m_nValue;path.pop_back();
}int main()
{BinaryTreeNode one1;one1.m_nValue = 10;BinaryTreeNode one2;one2.m_nValue = 5;BinaryTreeNode one3;one3.m_nValue = 12;BinaryTreeNode one4;one4.m_nValue = 4;BinaryTreeNode one5;one5.m_nValue = 7;one1.m_pLeft = &one2;one1.m_pRight = &one3;one2.m_pLeft = &one4;one2.m_pRight = &one5;one4.m_pLeft = NULL;one4.m_pRight = NULL;one5.m_pLeft = NULL;one5.m_pRight = NULL;one3.m_pLeft = NULL;one3.m_pRight = NULL;vector<int> res;FindPath(&one1, 22, res, 0);//system("pause");return 0;
}