題目：輸入一個(gè)整數(shù)和一棵二元樹,。從樹的根結(jié)點(diǎn)開始往下訪問一直到葉結(jié)點(diǎn)所經(jīng)過的所有結(jié)點(diǎn)形成一條路徑。打印出和與輸入整數(shù)相等的所有路徑,。
例如輸入整數(shù)22和如下二元樹
                                            10
                                           /   \
                                          5     12
                                        /   \   
                                      4     7 
則打印出兩條路徑：10, 12和10, 5, 7,。
二元樹結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義為：
struct BinaryTreeNode // a node in the binary tree
{
      int              m_nValue; // value of node
      BinaryTreeNode  *m_pLeft;  // left child of node
      BinaryTreeNode  *m_pRight; // right child of node
};
分析：這是百度的一道筆試題，考查對(duì)樹這種基本數(shù)據(jù)結(jié)構(gòu)以及遞歸函數(shù)的理解,。
當(dāng)訪問到某一結(jié)點(diǎn)時(shí),，把該結(jié)點(diǎn)添加到路徑上，并累加當(dāng)前結(jié)點(diǎn)的值,。如果當(dāng)前結(jié)點(diǎn)為葉結(jié)點(diǎn)并且當(dāng)前路徑的和剛好等于輸入的整數(shù),，則當(dāng)前的路徑符合要求，我們把它打印出來(lái),。如果當(dāng)前結(jié)點(diǎn)不是葉結(jié)點(diǎn),，則繼續(xù)訪問它的子結(jié)點(diǎn),。當(dāng)前結(jié)點(diǎn)訪問結(jié)束后，遞歸函數(shù)將自動(dòng)回到父結(jié)點(diǎn),。因此我們?cè)诤瘮?shù)退出之前要在路徑上刪除當(dāng)前結(jié)點(diǎn)并減去當(dāng)前結(jié)點(diǎn)的值,，以確保返回父結(jié)點(diǎn)時(shí)路徑剛好是根結(jié)點(diǎn)到父結(jié)點(diǎn)的路徑。我們不難看出保存路徑的數(shù)據(jù)結(jié)構(gòu)實(shí)際上是一個(gè)棧結(jié)構(gòu),，因?yàn)槁窂揭c遞歸調(diào)用狀態(tài)一致,，而遞歸調(diào)用本質(zhì)就是一個(gè)壓棧和出棧的過程。
參考代碼：
///////////////////////////////////////////////////////////////////////
// Find paths whose sum equal to expected sum
///////////////////////////////////////////////////////////////////////
void FindPath
(
      BinaryTreeNode*   pTreeNode,    // a node of binary tree
      int               expectedSum,  // the expected sum
      std::vector<int>& path,         // a path from root to current node
      int&              currentSum    // the sum of path
)
{
      if(!pTreeNode)
            return;
      currentSum += pTreeNode->m_nValue;
      path.push_back(pTreeNode->m_nValue);
      // if the node is a leaf, and the sum is same as pre-defined,
      // the path is what we want. print the path
      bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight);
      if(currentSum == expectedSum && isLeaf)
      {   
           std::vector<int>::iterator iter = path.begin();
           for(; iter != path.end(); ++ iter)
                 std::cout << *iter << '\t';
           std::cout << std::endl;
      }

      // if the node is not a leaf, goto its children
      if(pTreeNode->m_pLeft)
            FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);
      if(pTreeNode->m_pRight)
            FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum);

      // when we finish visiting a node and return to its parent node,
      // we should delete this node from the path and
      // minus the node's value from the current sum
      currentSum -= pTreeNode->m_nValue;
      path.pop_back();
}