生活随笔
收集整理的這篇文章主要介紹了
二叉树和为某种所有路径
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題目：輸入一個整數和一棵二元樹。打印出和與輸入整數相等的所有路徑，從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑。
分析：這道題考查對二叉樹遍歷方式的理解，采用后序遍歷，如果把二叉樹看成圖，就是圖的深度遍歷。使用變量存放當前遍歷的路徑和，當訪問到某一結點時，把該結點添加到路徑上，并累加當前結點的值。如果當前結點為葉結點并且當前路徑的和剛好等于輸入的整數，則當前的路徑符合要求，我們把它打印出來。如果當前結點不是葉結點，則繼續訪問它的子結點。當前結點訪問結束后，遞歸函數將自動回到父結點，因此我們在函數退出之前要在路徑上刪除當前結點并減去當前結點的值，以確保返回父結點時路徑剛好是根結點到父結點的路徑。
二元樹結點的數據結構定義為：
view plaincopy to clipboardprint?
struct?BSTreeNode?? {?? ????struct?BSTreeNode()?? ????{?? ????????m_pLeft?=?NULL;?? ????????m_pRight?=?NULL;?? ????}?? ????int?m_nValue;????????????? ????BSTreeNode?*m_pLeft;?????? ????BSTreeNode?*m_pRight;????? };?? 遞歸求解代碼如下：
view plaincopy to clipboardprint?
?? ?? ?? void?FindPath?? (?? ?BSTreeNode*????????pTreeNode,???????? ?int????????????????expectedSum,?????? ?std::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)?? ????{?? ????????std::vector<int>::iterator?iter?=?path.begin();?? ????????for(;?iter?!=?path.end();?++?iter)?? ????????????printf("%d\t",*iter);?? ????????printf("\n");?? ????}?? ?? ?????? ????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;//我認為沒有必要傳currentSum的引用，所以在這里也不需要減 ? ????path.pop_back();?? }?? </int></int>?? 擴展題：如果將條件放寬，計算和的路徑改為從根節點到葉子節點路徑上任意連續子路徑呢？
條件改變之后，難度有所增加，堆棧中光存放從root到當前節點的和顯然不夠，需要對堆棧中的元素做出改變，使之存放堆棧當前位置到當前遍歷節點的路徑和，元素類型定義如下：
view plaincopy to clipboardprint?
class?StackElement?? {?? public:?? ????StackElement(struct?BSTreeNode*?node,?int?s){pNode?=?node;sum?=?s;};?? ?? ????void?AddValue(int?v){sum+=v;}?? ????int?GetValue(){return?sum;}?? ?? ????struct?BSTreeNode*?pNode;????? ????int?sum;?????????????????????? };?? 在這里不適用遞歸，而采用另外的一種求解方式。
view plaincopy to clipboardprint?
void?BSTreeSumWay(struct?BSTreeNode*?root,int?sum)?? {?? ????assert(root);?? ?? ????vector<stackelement>?way;?? ?? ????while?(root?||?!way.empty())?? ????{?? ????????while(root)?? ????????{?? ?? ????????????StackElement?temp(root,0);?? ????????????way.push_back(temp);?? ?? ?????????????? ????????????vector<stackelement>::iterator?way_iter?=?way.begin();?? ????????????for?(;way_iter?!=?way.end();?way_iter++)?? ????????????{?? ????????????????way_iter->AddValue(root->m_nValue);?? ????????????????if?(sum?==?way_iter->GetValue())?? ????????????????{?? ?????????????????????? ????????????????????vector<stackelement>::iterator?print_iter?=?way_iter;?? ????????????????????for?(;print_iter?!=?way.end();print_iter++)?? ????????????????????{?? ????????????????????????printf("%d\t",print_iter->pNode->m_nValue);?? ????????????????????}?? ????????????????????printf("\n");?? ????????????????}?? ????????????}?? ?? ????????????root?=?root->m_pLeft;?? ????????}?? ?? ?????????? ????????while?(way.rbegin()->pNode->m_pRight==NULL?||?root==way.rbegin()->pNode->m_pRight)?? ????????{?? ?? ????????????root?=?way.rbegin()->pNode;?? ?? ?????????????? ????????????int?v?=?-way.rbegin()->pNode->m_nValue;?? ????????????way.pop_back();?? ????????????vector<stackelement>::iterator?way_iter?=?way.begin();?? ????????????for?(;way_iter?!=?way.end();?way_iter++)?? ????????????{?? ????????????????way_iter->AddValue(v);?? ????????????}?? ?? ????????????if?(way.empty())?? ????????????{?? ????????????????break;?? ????????????}?? ?? ????????}?? ?? ????????if?(way.empty())?? ????????????break;?? ?? ????????root?=?way.rbegin()->pNode->m_pRight;?? ?? ????}?? ?? }?? </stackelement></stackelement></stackelement></stackelement>?? 網絡轉載請注明：轉載自程序員面試之家
總結
以上是生活随笔為你收集整理的二叉树和为某种所有路径的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
