日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

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

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
二叉樹的遞歸遍歷，套路都在這里

二叉樹的遞歸遍歷

這次我們要好好談一談遞歸，為什么很多同學(xué)看遞歸算法都是“一看就會，一寫就廢”。

成都創(chuàng)新互聯(lián)始終致力于在企業(yè)網(wǎng)站建設(shè)領(lǐng)域發(fā)展。秉承“創(chuàng)新、求實、誠信、拼搏”的企業(yè)精神，致力為企業(yè)提供全面的網(wǎng)絡(luò)宣傳與技術(shù)應(yīng)用整體策劃方案，為企業(yè)提供包括“網(wǎng)站建設(shè)、成都響應(yīng)式網(wǎng)站建設(shè)、手機網(wǎng)站建設(shè)、微信網(wǎng)站建設(shè)、微信平臺小程序開發(fā)、商城網(wǎng)站開發(fā)、平臺網(wǎng)站建設(shè)秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

主要是對遞歸不成體系，沒有方法論，每次寫遞歸算法 ，都是靠玄學(xué)來寫代碼，代碼能不能編過都靠運氣。

本篇將介紹前后中序的遞歸寫法，一些同學(xué)可能會感覺很簡單，其實不然，我們要通過簡單題目把方法論確定下來，有了方法論，后面才能應(yīng)付復(fù)雜的遞歸。

這里幫助大家確定下來遞歸算法的三個要素。每次寫遞歸，都按照這三要素來寫，可以保證大家寫出正確的遞歸算法!

確定遞歸函數(shù)的參數(shù)和返回值：確定哪些參數(shù)是遞歸的過程中需要處理的，那么就在遞歸函數(shù)里加上這個參數(shù)， 并且還要明確每次遞歸的返回值是什么進而確定遞歸函數(shù)的返回類型。

確定終止條件：寫完了遞歸算法, 運行的時候，經(jīng)常會遇到棧溢出的錯誤，就是沒寫終止條件或者終止條件寫的不對，操作系統(tǒng)也是用一個棧的結(jié)構(gòu)來保存每一層遞歸的信息，如果遞歸沒有終止，操作系統(tǒng)的內(nèi)存棧必然就會溢出。

確定單層遞歸的邏輯：確定每一層遞歸需要處理的信息。在這里也就會重復(fù)調(diào)用自己來實現(xiàn)遞歸的過程。

好了，我們確認(rèn)了遞歸的三要素，接下來就來練練手：

以下以前序遍歷為例：

確定遞歸函數(shù)的參數(shù)和返回值：因為要打印出前序遍歷節(jié)點的數(shù)值，所以參數(shù)里需要傳入vector在放節(jié)點的數(shù)值，除了這一點就不需要在處理什么數(shù)據(jù)了也不需要有返回值，所以遞歸函數(shù)返回類型就是void，代碼如下：

 
 
 
    
  
  
  
  1. void traversal(TreeNode* cur, vector& vec)
    2.

確定終止條件：在遞歸的過程中，如何算是遞歸結(jié)束了呢，當(dāng)然是當(dāng)前遍歷的節(jié)點是空了，那么本層遞歸就要要結(jié)束了，所以如果當(dāng)前遍歷的這個節(jié)點是空，就直接return，代碼如下：

 
 
 
    
  
  
  
  1. if (cur == NULL) return;
    2.

確定單層遞歸的邏輯：前序遍歷是中左右的循序，所以在單層遞歸的邏輯，是要先取中節(jié)點的數(shù)值，代碼如下：

 
 
 
    
  
  
  
  1. vec.push_back(cur->val);    // 中
    2. 
  
  
  
  2. traversal(cur->left, vec);  // 左
    3. 
  
  
  
  3. traversal(cur->right, vec); // 右
    4.

單層遞歸的邏輯就是按照中左右的順序來處理的，這樣二叉樹的前序遍歷，基本就寫完了，在看一下完整代碼：

前序遍歷：

 
 
 
    
  
  
  
  1. class Solution {
    2. 
  
  
  
  2. public:
    3. 
  
  
  
  3.     void traversal(TreeNode* cur, vector& vec) {
    4. 
  
  
  
  4.         if (cur == NULL) return;
    5. 
  
  
  
  5.         vec.push_back(cur->val);    // 中
    6. 
  
  
  
  6.         traversal(cur->left, vec);  // 左
    7. 
  
  
  
  7.         traversal(cur->right, vec); // 右
    8. 
  
  
  
  8.     }
    9. 
  
  
  
  9.     vector preorderTraversal(TreeNode* root) {
    10. 
  
  
  
  10.         vector result;
    11. 
  
  
  
  11.         traversal(root, result);
    12. 
  
  
  
  12.         return result;
    13. 
  
  
  
  13.     }
    14. 
  
  
  
  14. };
    15.

那么前序遍歷寫出來之后，中序和后序遍歷就不難理解了，代碼如下：

中序遍歷：

 
 
 
    
  
  
  
  1. void traversal(TreeNode* cur, vector& vec) {
    2. 
  
  
  
  2.     if (cur == NULL) return;
    3. 
  
  
  
  3.     traversal(cur->left, vec);  // 左
    4. 
  
  
  
  4.     vec.push_back(cur->val);    // 中
    5. 
  
  
  
  5.     traversal(cur->right, vec); // 右
    6. 
  
  
  
  6. }
    7.

后序遍歷：

 
 
 
    
  
  
  
  1. void traversal(TreeNode* cur, vector& vec) {
    2. 
  
  
  
  2.     if (cur == NULL) return;
    3. 
  
  
  
  3.     traversal(cur->left, vec);  // 左
    4. 
  
  
  
  4.     traversal(cur->right, vec); // 右
    5. 
  
  
  
  5.     vec.push_back(cur->val);    // 中
    6. 
  
  
  
  6. }
    7.

此時大家可以做一做leetcode上三道題目，分別是：

  • 144.二叉樹的前序遍歷
  • 145.二叉樹的后序遍歷
  • 94.二叉樹的中序遍歷

可能有同學(xué)感覺前后中序遍歷的遞歸太簡單了，要打迭代法(非遞歸)，別急，我們明天打迭代法，打個通透!

其他語言版本

Java：

 
 
 
    
  
  
  
  1. // 前序遍歷·遞歸·LC144_二叉樹的前序遍歷
    2. 
  
  
  
  2. class Solution {
    3. 
  
  
  
  3.     ArrayList preOrderReverse(TreeNode root) {
    4. 
  
  
  
  4.         ArrayList result = new ArrayList();
    5. 
  
  
  
  5.         preOrder(root, result);
    6. 
  
  
  
  6.         return result;
    7. 
  
  
  
  7.     }
    8. 
  
  
  
  8. 
  
  
  
  9.     void preOrder(TreeNode root, ArrayList result) {
    10. 
  
  
  
  10.         if (root == null) {
    11. 
  
  
  
  11.             return;
    12. 
  
  
  
  12.         }
    13. 
  
  
  
  13.         result.add(root.val);           // 注意這一句
    14. 
  
  
  
  14.         preOrder(root.left, result);
    15. 
  
  
  
  15.         preOrder(root.right, result);
    16. 
  
  
  
  16.     }
    17. 
  
  
  
  17. }
    18. 
  
  
  
  18. // 中序遍歷·遞歸·LC94_二叉樹的中序遍歷
    19. 
  
  
  
  19. class Solution {
    20. 
  
  
  
  20.     public List inorderTraversal(TreeNode root) {
    21. 
  
  
  
  21.         List res = new ArrayList<>();
    22. 
  
  
  
  22.         inorder(root, res);
    23. 
  
  
  
  23.         return res;
    24. 
  
  
  
  24.     }
    25. 
  
  
  
  25. 
  
  
  
  26.     void inorder(TreeNode root, List list) {
    27. 
  
  
  
  27.         if (root == null) {
    28. 
  
  
  
  28.             return;
    29. 
  
  
  
  29.         }
    30. 
  
  
  
  30.         inorder(root.left, list);
    31. 
  
  
  
  31.         list.add(root.val);             // 注意這一句
    32. 
  
  
  
  32.         inorder(root.right, list);
    33. 
  
  
  
  33.     }
    34. 
  
  
  
  34. }
    35. 
  
  
  
  35. // 后序遍歷·遞歸·LC145_二叉樹的后序遍歷
    36. 
  
  
  
  36. class Solution {
    37. 
  
  
  
  37.     public List postorderTraversal(TreeNode root) {
    38. 
  
  
  
  38.         List res = new ArrayList<>();
    39. 
  
  
  
  39.         postorder(root, res);
    40. 
  
  
  
  40.         return res;
    41. 
  
  
  
  41.     }
    42. 
  
  
  
  42. 
  
  
  
  43.     void postorder(TreeNode root, List list) {
    44. 
  
  
  
  44.         if (root == null) {
    45. 
  
  
  
  45.             return;
    46. 
  
  
  
  46.         }
    47. 
  
  
  
  47.         postorder(root.left, list);
    48. 
  
  
  
  48.         postorder(root.right, list);
    49. 
  
  
  
  49.         list.add(root.val);             // 注意這一句
    50. 
  
  
  
  50.     }
    51. 
  
  
  
  51. }
    52.

Python：

 
 
 
    
  
  
  
  1. # 前序遍歷-遞歸-LC144_二叉樹的前序遍歷
    2. 
  
  
  
  2. class Solution:
    3. 
  
  
  
  3.     def preorderTraversal(self, root: TreeNode) -> List[int]:
    4. 
  
  
  
  4.         # 保存結(jié)果
    5. 
  
  
  
  5.         result = []
    6. 
  
  
  
  6.         
    7. 
  
  
  
  7.         def traversal(root: TreeNode):
    8. 
  
  
  
  8.             if root == None:
    9. 
  
  
  
  9.                 return
    10. 
  
  
  
  10.             result.append(root.val) # 前序
    11. 
  
  
  
  11.             traversal(root.left)    # 左
    12. 
  
  
  
  12.             traversal(root.right)   # 右
    13. 
  
  
  
  13. 
  
  
  
  14.         traversal(root)
    15. 
  
  
  
  15.         return result
    16. 
  
  
  
  16. 
  
  
  
  17. # 中序遍歷-遞歸-LC94_二叉樹的中序遍歷
    18. 
  
  
  
  18. class Solution:
    19. 
  
  
  
  19.     def inorderTraversal(self, root: TreeNode) -> List[int]:
    20. 
  
  
  
  20.         result = []
    21. 
  
  
  
  21. 
  
  
  
  22.         def traversal(root: TreeNode):
    23. 
  
  
  
  23.             if root == None:
    24. 
  
  
  
  24.                 return
    25. 
  
  
  
  25.             traversal(root.left)    # 左
    26. 
  
  
  
  26.             result.append(root.val) # 中序
    27. 
  
  
  
  27.             traversal(root.right)   # 右
    28. 
  
  
  
  28. 
  
  
  
  29.         traversal(root)
    30. 
  
  
  
  30.         return result
    31. 
  
  
  
  31. 
  
  
  
  32. # 后序遍歷-遞歸-LC145_二叉樹的后序遍歷
    33. 
  
  
  
  33. class Solution:
    34. 
  
  
  
  34.     def postorderTraversal(self, root: TreeNode) -> List[int]:
    35. 
  
  
  
  35.         result = []
    36. 
  
  
  
  36. 
  
  
  
  37.         def traversal(root: TreeNode):
    38. 
  
  
  
  38.             if root == None:
    39. 
  
  
  
  39.                 return
    40. 
  
  
  
  40.             traversal(root.left)    # 左
    41. 
  
  
  
  41.             traversal(root.right)   # 右
    42. 
  
  
  
  42.             result.append(root.val) # 后序
    43. 
  
  
  
  43. 
  
  
  
  44.         traversal(root)
    45. 
  
  
  
  45.         return result
    46.

網(wǎng)站標(biāo)題：二叉樹的遞歸遍歷，套路都在這里
標(biāo)題鏈接：http://www.dlmjj.cn/article/cdohgje.html