日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
遞歸函數(shù)什么時(shí)候要有返回值，什么時(shí)候沒有返回值？

相信很多同學(xué)都會(huì)疑惑，遞歸函數(shù)什么時(shí)候要有返回值，什么時(shí)候沒有返回值，特別是有的時(shí)候遞歸函數(shù)返回類型為bool類型。

那么接下來我通過詳細(xì)講解如下兩道題，來回答這個(gè)問題：

  • 112.路徑總和
  • 113.路徑總和ii

112. 路徑總和

題目地址：https://leetcode-cn.com/problems/path-sum/

給定一個(gè)二叉樹和一個(gè)目標(biāo)和，判斷該樹中是否存在根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和。

說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例: 給定如下二叉樹，以及目標(biāo)和 sum = 22，

返回 true, 因?yàn)榇嬖谀繕?biāo)和為 22 的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑 5->4->11->2。

思路

這道題我們要遍歷從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的的路徑看看總和是不是目標(biāo)和。

遞歸

可以使用深度優(yōu)先遍歷的方式(本題前中后序都可以，無所謂，因?yàn)橹泄?jié)點(diǎn)也沒有處理邏輯)來遍歷二叉樹

  • 確定遞歸函數(shù)的參數(shù)和返回類型

參數(shù)：需要二叉樹的根節(jié)點(diǎn)，還需要一個(gè)計(jì)數(shù)器，這個(gè)計(jì)數(shù)器用來計(jì)算二叉樹的一條邊之和是否正好是目標(biāo)和，計(jì)數(shù)器為int型。

再來看返回值，遞歸函數(shù)什么時(shí)候需要返回值?什么時(shí)候不需要返回值?這里總結(jié)如下三點(diǎn)：

  • 如果需要搜索整顆二叉樹且不用處理遞歸返回值，遞歸函數(shù)就不要返回值。(這種情況就是本文下半部分介紹的113.路徑總和ii)
  • 如果需要搜索整顆二叉樹且需要處理遞歸返回值，遞歸函數(shù)就需要返回值。(這種情況我們?cè)?36. 二叉樹的最近公共祖先介紹)
  • 如果要搜索其中一條符合條件的路徑，那么遞歸一定需要返回值，因?yàn)橛龅椒蠗l件的路徑了就要及時(shí)返回。(本題的情況)

而本題我們要找一條符合條件的路徑，所以遞歸函數(shù)需要返回值，及時(shí)返回，那么返回類型是什么呢?

如圖所示：

112.路徑總和

圖中可以看出，遍歷的路線，并不要遍歷整棵樹，所以遞歸函數(shù)需要返回值，可以用bool類型表示。

所以代碼如下：

  
 
 
 
    
   
  
  
  
  1. bool traversal(treenode* cur, int count) // 注意函數(shù)的返回類型 
    2.
  • 確定終止條件

首先計(jì)數(shù)器如何統(tǒng)計(jì)這一條路徑的和呢?

不要去累加然后判斷是否等于目標(biāo)和，那么代碼比較麻煩，可以用遞減，讓計(jì)數(shù)器count初始為目標(biāo)和，然后每次減去遍歷路徑節(jié)點(diǎn)上的數(shù)值。

如果最后count == 0，同時(shí)到了葉子節(jié)點(diǎn)的話，說明找到了目標(biāo)和。

如果遍歷到了葉子節(jié)點(diǎn)，count不為0，就是沒找到。

遞歸終止條件代碼如下：

  
 
 
 
    
   
  
  
  
  1. if (!cur->left && !cur->right && count == 0) return true; // 遇到葉子節(jié)點(diǎn)，并且計(jì)數(shù)為0 
    2. 
   
  
  
  
  2. if (!cur->left && !cur->right) return false; // 遇到葉子節(jié)點(diǎn)而沒有找到合適的邊，直接返回 
    3.
  • 確定單層遞歸的邏輯

因?yàn)榻K止條件是判斷葉子節(jié)點(diǎn)，所以遞歸的過程中就不要讓空節(jié)點(diǎn)進(jìn)入遞歸了。

遞歸函數(shù)是有返回值的，如果遞歸函數(shù)返回true，說明找到了合適的路徑，應(yīng)該立刻返回。

代碼如下：

  
 
 
 
    
   
  
  
  
  1. if (cur->left) { // 左 （空節(jié)點(diǎn)不遍歷） 
    2. 
   
  
  
  
  2.     // 遇到葉子節(jié)點(diǎn)返回true，則直接返回true 
    3. 
   
  
  
  
  3.     if (traversal(cur->left, count - cur->left->val)) return true; // 注意這里有回溯的邏輯 
    4. 
   
  
  
  
  4. } 
    5. 
   
  
  
  
  5. if (cur->right) { // 右 （空節(jié)點(diǎn)不遍歷） 
    6. 
   
  
  
  
  6.     // 遇到葉子節(jié)點(diǎn)返回true，則直接返回true 
    7. 
   
  
  
  
  7.     if (traversal(cur->right, count - cur->right->val)) return true; // 注意這里有回溯的邏輯 
    8. 
   
  
  
  
  8. } 
    9. 
   
  
  
  
  9. return false; 
    10.

以上代碼中是包含著回溯的，沒有回溯，如何后撤重新找另一條路徑呢。

回溯隱藏在traversal(cur->left, count - cur->left->val)這里， 因?yàn)榘裞ount - cur->left->val 直接作為參數(shù)傳進(jìn)去，函數(shù)結(jié)束，count的數(shù)值沒有改變。

為了把回溯的過程體現(xiàn)出來，可以改為如下代碼：

  
 
 
 
    
   
  
  
  
  1. if (cur->left) { // 左 
    2. 
   
  
  
  
  2.     count -= cur->left->val; // 遞歸，處理節(jié)點(diǎn); 
    3. 
   
  
  
  
  3.     if (traversal(cur->left, count)) return true; 
    4. 
   
  
  
  
  4.     count += cur->left->val; // 回溯，撤銷處理結(jié)果 
    5. 
   
  
  
  
  5. } 
    6. 
   
  
  
  
  6. if (cur->right) { // 右 
    7. 
   
  
  
  
  7.     count -= cur->right->val; 
    8. 
   
  
  
  
  8.     if (traversal(cur->right, count)) return true; 
    9. 
   
  
  
  
  9.     count += cur->right->val; 
    10. 
   
  
  
  
  10. } 
    11. 
   
  
  
  
  11. return false; 
    12.

整體代碼如下：

  
 
 
 
    
   
  
  
  
  1. class solution { 
    2. 
   
  
  
  
  2. private: 
    3. 
   
  
  
  
  3.     bool traversal(treenode* cur, int count) { 
    4. 
   
  
  
  
  4.         if (!cur->left && !cur->right && count == 0) return true; // 遇到葉子節(jié)點(diǎn)，并且計(jì)數(shù)為0 
    5. 
   
  
  
  
  5.         if (!cur->left && !cur->right) return false; // 遇到葉子節(jié)點(diǎn)直接返回 
    6. 
   
  
  
  
  6.  
    7. 
   
  
  
  
  7.         if (cur->left) { // 左 
    8. 
   
  
  
  
  8.             count -= cur->left->val; // 遞歸，處理節(jié)點(diǎn); 
    9. 
   
  
  
  
  9.             if (traversal(cur->left, count)) return true; 
    10. 
   
  
  
  
  10.             count += cur->left->val; // 回溯，撤銷處理結(jié)果 
    11. 
   
  
  
  
  11.         } 
    12. 
   
  
  
  
  12.         if (cur->right) { // 右 
    13. 
   
  
  
  
  13.             count -= cur->right->val; // 遞歸，處理節(jié)點(diǎn); 
    14. 
   
  
  
  
  14.             if (traversal(cur->right, count)) return true; 
    15. 
   
  
  
  
  15.             count += cur->right->val; // 回溯，撤銷處理結(jié)果 
    16. 
   
  
  
  
  16.         } 
    17. 
   
  
  
  
  17.         return false; 
    18. 
   
  
  
  
  18.     } 
    19. 
   
  
  
  
  19.  
    20. 
   
  
  
  
  20. public: 
    21. 
   
  
  
  
  21.     bool haspathsum(treenode* root, int sum) { 
    22. 
   
  
  
  
  22.         if (root == null) return false; 
    23. 
   
  
  
  
  23.         return traversal(root, sum - root->val); 
    24. 
   
  
  
  
  24.     } 
    25. 
   
  
  
  
  25. }; 
    26.

以上代碼精簡之后如下：

  
 
 
 
    
   
  
  
  
  1. class solution { 
    2. 
   
  
  
  
  2. public: 
    3. 
   
  
  
  
  3.     bool haspathsum(treenode* root, int sum) { 
    4. 
   
  
  
  
  4.         if (root == null) return false; 
    5. 
   
  
  
  
  5.         if (!root->left && !root->right && sum == root->val) { 
    6. 
   
  
  
  
  6.             return true; 
    7. 
   
  
  
  
  7.         } 
    8. 
   
  
  
  
  8.         return haspathsum(root->left, sum - root->val) || haspathsum(root->right, sum - root->val); 
    9. 
   
  
  
  
  9.     } 
    10. 
   
  
  
  
  10. }; 
    11.

是不是發(fā)現(xiàn)精簡之后的代碼，已經(jīng)完全看不出分析的過程了，所以我們要把題目分析清楚之后，在追求代碼精簡。 這一點(diǎn)我已經(jīng)強(qiáng)調(diào)很多次了!

迭代

如果使用棧模擬遞歸的話，那么如果做回溯呢?

此時(shí)棧里一個(gè)元素不僅要記錄該節(jié)點(diǎn)指針，還要記錄從頭結(jié)點(diǎn)到該節(jié)點(diǎn)的路徑數(shù)值總和。

c++就我們用pair結(jié)構(gòu)來存放這個(gè)棧里的元素。

定義為：pair

這個(gè)為棧里的一個(gè)元素。

如下代碼是使用棧模擬的前序遍歷，如下：(詳細(xì)注釋)

  
 
 
 
    
   
  
  
  
  1. class solution { 
    2. 
   
  
  
  
  2.  
    3. 
   
  
  
  
  3. public: 
    4. 
   
  
  
  
  4.     bool haspathsum(treenode* root, int sum) { 
    5. 
   
  
  
  
  5.         if (root == null) return false; 
    6. 
   
  
  
  
  6.         // 此時(shí)棧里要放的是pair<節(jié)點(diǎn)指針，路徑數(shù)值> 
    7. 
   
  
  
  
  7.         stack> st; 
    8. 
   
  
  
  
  8.         st.push(pair(root, root->val)); 
    9. 
   
  
  
  
  9.         while (!st.empty()) { 
    10. 
   
  
  
  
  10.             pair node = st.top(); 
    11. 
   
  
  
  
  11.             st.pop(); 
    12. 
   
  
  
  
  12.             // 如果該節(jié)點(diǎn)是葉子節(jié)點(diǎn)了，同時(shí)該節(jié)點(diǎn)的路徑數(shù)值等于sum，那么就返回true 
    13. 
   
  
  
  
  13.             if (!node.first->left && !node.first->right && sum == node.second) return true; 
    14. 
   
  
  
  
  14.  
    15. 
   
  
  
  
  15.             // 右節(jié)點(diǎn)，壓進(jìn)去一個(gè)節(jié)點(diǎn)的時(shí)候，將該節(jié)點(diǎn)的路徑數(shù)值也記錄下來 
    16. 
   
  
  
  
  16.             if (node.first->right) { 
    17. 
   
  
  
  
  17.                 st.push(pair(node.first->right, node.second + node.first->right->val)); 
    18. 
   
  
  
  
  18.             } 
    19. 
   
  
  
  
  19.  
    20. 
   
  
  
  
  20.             // 左節(jié)點(diǎn)，壓進(jìn)去一個(gè)節(jié)點(diǎn)的時(shí)候，將該節(jié)點(diǎn)的路徑數(shù)值也記錄下來 
    21. 
   
  
  
  
  21.             if (node.first->left) { 
    22. 
   
  
  
  
  22.                 st.push(pair(node.first->left, node.second + node.first->left->val)); 
    23. 
   
  
  
  
  23.             } 
    24. 
   
  
  
  
  24.         } 
    25. 
   
  
  
  
  25.         return false; 
    26. 
   
  
  
  
  26.     } 
    27. 
   
  
  
  
  27. }; 
    28.

如果大家完全理解了本地的遞歸方法之后，就可以順便把leetcode上113. 路徑總和ii做了。

113. 路徑總和ii

題目地址：https://leetcode-cn.com/problems/path-sum-ii/

給定一個(gè)二叉樹和一個(gè)目標(biāo)和，找到所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑總和等于給定目標(biāo)和的路徑。

說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例: 給定如下二叉樹，以及目標(biāo)和 sum = 22，

思路

113.路徑總和ii要遍歷整個(gè)樹，找到所有路徑，所以遞歸函數(shù)不要返回值!

如圖：

113.路徑總和ii

為了盡可能的把細(xì)節(jié)體現(xiàn)出來，我寫出如下代碼(這份代碼并不簡潔，但是邏輯非常清晰)

  
 
 
 
    
   
  
  
  
  1. class solution { 
    2. 
   
  
  
  
  2. private: 
    3. 
   
  
  
  
  3.     vector> result; 
    4. 
   
  
  
  
  4.     vector path; 
    5. 
   
  
  
  
  5.     // 遞歸函數(shù)不需要返回值，因?yàn)槲覀円闅v整個(gè)樹 
    6. 
   
  
  
  
  6.     void traversal(treenode* cur, int count) { 
    7. 
   
  
  
  
  7.         if (!cur->left && !cur->right && count == 0) { // 遇到了葉子節(jié)點(diǎn)且找到了和為sum的路徑 
    8. 
   
  
  
  
  8.             result.push_back(path); 
    9. 
   
  
  
  
  9.             return; 
    10. 
   
  
  
  
  10.         } 
    11. 
   
  
  
  
  11.  
    12. 
   
  
  
  
  12.         if (!cur->left && !cur->right) return ; // 遇到葉子節(jié)點(diǎn)而沒有找到合適的邊，直接返回 
    13. 
   
  
  
  
  13.  
    14. 
   
  
  
  
  14.         if (cur->left) { // 左 （空節(jié)點(diǎn)不遍歷） 
    15. 
   
  
  
  
  15.             path.push_back(cur->left->val); 
    16. 
   
  
  
  
  16.             count -= cur->left->val; 
    17. 
   
  
  
  
  17.             traversal(cur->left, count);    // 遞歸 
    18. 
   
  
  
  
  18.             count += cur->left->val;        // 回溯 
    19. 
   
  
  
  
  19.             path.pop_back();                // 回溯 
    20. 
   
  
  
  
  20.         } 
    21. 
   
  
  
  
  21.         if (cur->right) { // 右 （空節(jié)點(diǎn)不遍歷） 
    22. 
   
  
  
  
  22.             path.push_back(cur->right->val); 
    23. 
   
  
  
  
  23.             count -= cur->right->val; 
    24. 
   
  
  
  
  24.             traversal(cur->right, count);   // 遞歸 
    25. 
   
  
  
  
  25.             count += cur->right->val;       // 回溯 
    26. 
   
  
  
  
  26.             path.pop_back();                // 回溯 
    27. 
   
  
  
  
  27.         } 
    28. 
   
  
  
  
  28.         return ; 
    29. 
   
  
  
  
  29.     } 
    30. 
   
  
  
  
  30.  
    31. 
   
  
  
  
  31. public: 
    32. 
   
  
  
  
  32.     vector> pathsum(treenode* root, int sum) { 
    33. 
   
  
  
  
  33.         result.clear(); 
    34. 
   
  
  
  
  34.         path.clear(); 
    35. 
   
  
  
  
  35.         if (root == null) return result; 
    36. 
   
  
  
  
  36.         path.push_back(root->val); // 把根節(jié)點(diǎn)放進(jìn)路徑 
    37. 
   
  
  
  
  37.         traversal(root, sum - root->val); 
    38. 
   
  
  
  
  38.         return result; 
    39. 
   
  
  
  
  39.     } 
    40. 
   
  
  
  
  40. }; 
    41.

至于113. 路徑總和ii 的迭代法我并沒有寫，用迭代方式記錄所有路徑比較麻煩，也沒有必要，如果大家感興趣的話，可以再深入研究研究。

總結(jié)

本篇通過leetcode上112. 路徑總和 和 113. 路徑總和ii 詳細(xì)的講解了 遞歸函數(shù)什么時(shí)候需要返回值，什么不需要返回值。

這兩道題目是掌握這一知識(shí)點(diǎn)非常好的題目，大家看完本篇文章再去做題，就會(huì)感受到搜索整棵樹和搜索某一路徑的差別。

對(duì)于112. 路徑總和，我依然給出了遞歸法和迭代法，這種題目其實(shí)用迭代法會(huì)復(fù)雜一些，能掌握遞歸方式就夠了!

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。


本文名稱：遞歸函數(shù)什么時(shí)候要有返回值，什么時(shí)候沒有返回值？
本文地址：http://m.5511xx.com/article/coggieh.html