二叉樹中和為某一值的路徑

題目:

輸入一棵一二叉樹和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。

二義樹結點的定義如下:

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