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

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

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
二叉樹：一入遞歸深似海，從此offer是路人

 一看就會，一寫就廢!

創(chuàng)新互聯(lián)是一家專業(yè)提供荔灣企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站建設(shè)、成都網(wǎng)站制作、H5技術(shù)、小程序制作等業(yè)務(wù)。10年已為荔灣眾多企業(yè)、政府機構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)的建站公司優(yōu)惠進行中。

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

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

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

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

  1. 「確定遞歸函數(shù)的參數(shù)和返回值：」確定哪些參數(shù)是遞歸的過程中需要處理的，那么就在遞歸函數(shù)里加上這個參數(shù)， 并且還要明確每次遞歸的返回值是什么進而確定遞歸函數(shù)的返回類型。
  2. 「確定終止條件：」寫完了遞歸算法, 運行的時候，經(jīng)常會遇到棧溢出的錯誤，就是沒寫終止條件或者終止條件寫的不對，操作系統(tǒng)也是用一個棧的結(jié)構(gòu)來保存每一層遞歸的信息，如果遞歸沒有終止，操作系統(tǒng)的內(nèi)存棧必然就會溢出。
  3. 「確定單層遞歸的邏輯：」確定每一層遞歸需要處理的信息。在這里也就會重復(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é)感覺前后中序遍歷的遞歸太簡單了，要打迭代法(非遞歸)，別急，我們明天打前中后序的迭代法，打個通透!

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


分享文章：二叉樹：一入遞歸深似海，從此offer是路人
URL分享：http://www.5511xx.com/article/dhgpihh.html