題目：輸入一個(gè)整數(shù)和一棵二元樹(shù)。從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下訪問(wèn)一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的所有結(jié)點(diǎn)形成一條路徑。打印出和與輸入整數(shù)相等的所有路徑。

例如輸入整數(shù)22和如下二元樹(shù)

??????????????????????????????????????????? 10
?????????????????????????????????????????? /?? \
????????????????????????????????????????? 5???? 12
? ????????????????????????????????????? / ? \???
???????? ??????????????????????????? 　4???? 7?

則打印出兩條路徑：10, 12和10, 5, 7。

二元樹(shù)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義為：

struct BinaryTreeNode // a node in the binary tree {int m_nValue; // value of nodeBinaryTreeNode *m_pLeft; // left child of nodeBinaryTreeNode *m_pRight; // right child of node };

分析：這是百度的一道筆試題，考查對(duì)樹(shù)這種基本數(shù)據(jù)結(jié)構(gòu)以及遞歸函數(shù)的理解。

當(dāng)訪問(wèn)到某一結(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ù)訪問(wèn)它的子結(jié)點(diǎn)。當(dāng)前結(jié)點(diǎn)訪問(wè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è)壓棧和出棧的過(guò)程。

參考代碼：

/// // Find paths whose sum equal to expected sum /// void FindPath (BinaryTreeNode* pTreeNode, // a node of binary treeint expectedSum, // the expected sumstd::vector<int>& path, // a path from root to current nodeint& 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 pathbool 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 childrenif(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 sumcurrentSum -= pTreeNode->m_nValue;path.pop_back(); }

本文已經(jīng)收錄到《劍指Offer——名企面試官精講典型編程題》一書(shū)中，有改動(dòng)，書(shū)中的分析講解更加詳細(xì)。歡迎關(guān)注。我在英文版博客http://codercareer.blogspot.com/2011/09/no-04-paths-with-specified-sum-in.html也討論了這個(gè)題目，感興趣的讀者可以參考。

本題已被九度Online Judge系統(tǒng)收錄，歡迎讀者移步到http://ac.jobdu.com/hhtproblems.php在線測(cè)試自己的代碼。

博主何海濤對(duì)本博客文章享有版權(quán)。網(wǎng)絡(luò)轉(zhuǎn)載請(qǐng)注明出處http://zhedahht.blog.163.com/。整理出版物請(qǐng)和作者聯(lián)系。對(duì)解題思路有任何建議，歡迎在評(píng)論中告知，或者加我微博http://weibo.com/zhedahht或者http://t.163.com/zhedahht與我討論。謝謝。

總結(jié)

以上是生活随笔為你收集整理的程序员面试题精选100题(04)－二元树中和为某一值的所有路径[数据结构]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。