題目:
輸入一棵一二叉樹和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。
二義樹結點的定義如下:
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();
}
二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm
