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

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

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
聽說(shuō)遞歸能做的，棧也能做！

[[411457]]

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，作者程序員Carl 。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。

成都創(chuàng)新互聯(lián)是一家朝氣蓬勃的網(wǎng)站建設(shè)公司。公司專注于為企業(yè)提供信息化建設(shè)解決方案。從事網(wǎng)站開發(fā)，網(wǎng)站制作，網(wǎng)站設(shè)計(jì)，網(wǎng)站模板，微信公眾號(hào)開發(fā)，軟件開發(fā)，小程序開發(fā)，10年建站對(duì)成都混凝土泵車等多個(gè)方面，擁有多年的網(wǎng)站推廣經(jīng)驗(yàn)。

二叉樹的迭代遍歷

看完本篇大家可以使用迭代法，再重新解決如下三道leetcode上的題目：

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

為什么可以用迭代法(非遞歸的方式)來(lái)實(shí)現(xiàn)二叉樹的前后中序遍歷呢?

我們?cè)跅Ｅc隊(duì)列：匹配問題都是棧的強(qiáng)項(xiàng)中提到了，遞歸的實(shí)現(xiàn)就是：每一次遞歸調(diào)用都會(huì)把函數(shù)的局部變量、參數(shù)值和返回地址等壓入調(diào)用棧中，然后遞歸返回的時(shí)候，從棧頂彈出上一次遞歸的各項(xiàng)參數(shù)，所以這就是遞歸為什么可以返回上一層位置的原因。

此時(shí)大家應(yīng)該知道我們用棧也可以是實(shí)現(xiàn)二叉樹的前后中序遍歷了。

前序遍歷(迭代法)

我們先看一下前序遍歷。

前序遍歷是中左右，每次先處理的是中間節(jié)點(diǎn)，那么先將跟節(jié)點(diǎn)放入棧中，然后將右孩子加入棧，再加入左孩子。

為什么要先加入 右孩子，再加入左孩子呢?因?yàn)檫@樣出棧的時(shí)候才是中左右的順序。

動(dòng)畫如下：

不難寫出如下代碼: (注意代碼中空節(jié)點(diǎn)不入棧)

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2. public: 
    3. 
  
  
  
  
  3.     vector preorderTraversal(TreeNode* root) { 
    4. 
  
  
  
  
  4.         stack st; 
    5. 
  
  
  
  
  5.         vector result; 
    6. 
  
  
  
  
  6.         if (root == NULL) return result; 
    7. 
  
  
  
  
  7.         st.push(root); 
    8. 
  
  
  
  
  8.         while (!st.empty()) { 
    9. 
  
  
  
  
  9.             TreeNode* node = st.top();                       // 中 
    10. 
  
  
  
  
  10.             st.pop(); 
    11. 
  
  
  
  
  11.             result.push_back(node->val); 
    12. 
  
  
  
  
  12.             if (node->right) st.push(node->right);           // 右（空節(jié)點(diǎn)不入棧） 
    13. 
  
  
  
  
  13.             if (node->left) st.push(node->left);             // 左（空節(jié)點(diǎn)不入棧） 
    14. 
  
  
  
  
  14.         } 
    15. 
  
  
  
  
  15.         return result; 
    16. 
  
  
  
  
  16.     } 
    17. 
  
  
  
  
  17. }; 
    18.

此時(shí)會(huì)發(fā)現(xiàn)貌似使用迭代法寫出前序遍歷并不難，確實(shí)不難。

此時(shí)是不是想改一點(diǎn)前序遍歷代碼順序就把中序遍歷搞出來(lái)了?

其實(shí)還真不行!

但接下來(lái)，再用迭代法寫中序遍歷的時(shí)候，會(huì)發(fā)現(xiàn)套路又不一樣了，目前的前序遍歷的邏輯無(wú)法直接應(yīng)用到中序遍歷上。

中序遍歷(迭代法)

為了解釋清楚，我說(shuō)明一下 剛剛在迭代的過(guò)程中，其實(shí)我們有兩個(gè)操作：

處理：將元素放進(jìn)result數(shù)組中

訪問：遍歷節(jié)點(diǎn)

分析一下為什么剛剛寫的前序遍歷的代碼，不能和中序遍歷通用呢，因?yàn)榍靶虮闅v的順序是中左右，先訪問的元素是中間節(jié)點(diǎn)，要處理的元素也是中間節(jié)點(diǎn)，所以剛剛才能寫出相對(duì)簡(jiǎn)潔的代碼，因?yàn)橐L問的元素和要處理的元素順序是一致的，都是中間節(jié)點(diǎn)。

那么再看看中序遍歷，中序遍歷是左中右，先訪問的是二叉樹頂部的節(jié)點(diǎn)，然后一層一層向下訪問，直到到達(dá)樹左面的最底部，再開始處理節(jié)點(diǎn)(也就是在把節(jié)點(diǎn)的數(shù)值放進(jìn)result數(shù)組中)，這就造成了處理順序和訪問順序是不一致的。

那么在使用迭代法寫中序遍歷，就需要借用指針的遍歷來(lái)幫助訪問節(jié)點(diǎn)，棧則用來(lái)處理節(jié)點(diǎn)上的元素。

動(dòng)畫如下：

中序遍歷，可以寫出如下代碼：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2. public: 
    3. 
  
  
  
  
  3.     vector inorderTraversal(TreeNode* root) { 
    4. 
  
  
  
  
  4.         vector result; 
    5. 
  
  
  
  
  5.         stack st; 
    6. 
  
  
  
  
  6.         TreeNode* cur = root; 
    7. 
  
  
  
  
  7.         while (cur != NULL || !st.empty()) { 
    8. 
  
  
  
  
  8.             if (cur != NULL) { // 指針來(lái)訪問節(jié)點(diǎn)，訪問到最底層 
    9. 
  
  
  
  
  9.                 st.push(cur); // 將訪問的節(jié)點(diǎn)放進(jìn)棧 
    10. 
  
  
  
  
  10.                 cur = cur->left;                // 左 
    11. 
  
  
  
  
  11.             } else { 
    12. 
  
  
  
  
  12.                 cur = st.top(); // 從棧里彈出的數(shù)據(jù)，就是要處理的數(shù)據(jù)（放進(jìn)result數(shù)組里的數(shù)據(jù)） 
    13. 
  
  
  
  
  13.                 st.pop(); 
    14. 
  
  
  
  
  14.                 result.push_back(cur->val);     // 中 
    15. 
  
  
  
  
  15.                 cur = cur->right;               // 右 
    16. 
  
  
  
  
  16.             } 
    17. 
  
  
  
  
  17.         } 
    18. 
  
  
  
  
  18.         return result; 
    19. 
  
  
  
  
  19.     } 
    20. 
  
  
  
  
  20. }; 
    21.

后序遍歷(迭代法)

再來(lái)看后序遍歷，先序遍歷是中左右，后續(xù)遍歷是左右中，那么我們只需要調(diào)整一下先序遍歷的代碼順序，就變成中右左的遍歷順序，然后在反轉(zhuǎn)result數(shù)組，輸出的結(jié)果順序就是左右中了，如下圖：

所以后序遍歷只需要前序遍歷的代碼稍作修改就可以了，代碼如下：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2. public: 
    3. 
  
  
  
  
  3.     vector postorderTraversal(TreeNode* root) { 
    4. 
  
  
  
  
  4.         stack st; 
    5. 
  
  
  
  
  5.         vector result; 
    6. 
  
  
  
  
  6.         if (root == NULL) return result; 
    7. 
  
  
  
  
  7.         st.push(root); 
    8. 
  
  
  
  
  8.         while (!st.empty()) { 
    9. 
  
  
  
  
  9.             TreeNode* node = st.top(); 
    10. 
  
  
  
  
  10.             st.pop(); 
    11. 
  
  
  
  
  11.             result.push_back(node->val); 
    12. 
  
  
  
  
  12.             if (node->left) st.push(node->left); // 相對(duì)于前序遍歷，這更改一下入棧順序 （空節(jié)點(diǎn)不入棧） 
    13. 
  
  
  
  
  13.             if (node->right) st.push(node->right); // 空節(jié)點(diǎn)不入棧 
    14. 
  
  
  
  
  14.         } 
    15. 
  
  
  
  
  15.         reverse(result.begin(), result.end()); // 將結(jié)果反轉(zhuǎn)之后就是左右中的順序了 
    16. 
  
  
  
  
  16.         return result; 
    17. 
  
  
  
  
  17.     } 
    18. 
  
  
  
  
  18. }; 
    19.

總結(jié)

此時(shí)我們用迭代法寫出了二叉樹的前后中序遍歷，大家可以看出前序和中序是完全兩種代碼風(fēng)格，并不想遞歸寫法那樣代碼稍做調(diào)整，就可以實(shí)現(xiàn)前后中序。

這是因?yàn)榍靶虮闅v中訪問節(jié)點(diǎn)(遍歷節(jié)點(diǎn))和處理節(jié)點(diǎn)(將元素放進(jìn)result數(shù)組中)可以同步處理，但是中序就無(wú)法做到同步!

上面這句話，可能一些同學(xué)不太理解，建議自己親手用迭代法，先寫出來(lái)前序，再試試能不能寫出中序，就能理解了。

那么問題又來(lái)了，難道 二叉樹前后中序遍歷的迭代法實(shí)現(xiàn)，就不能風(fēng)格統(tǒng)一么(即前序遍歷 改變代碼順序就可以實(shí)現(xiàn)中序 和 后序)?

當(dāng)然可以，這種寫法，還不是很好理解，我們將在下一篇文章里重點(diǎn)講解，敬請(qǐng)期待!

其他語(yǔ)言版本

Java：

 
 
 
 
    
  
  
  
  
  1. // 前序遍歷順序：中-左-右，入棧順序：中-右-左 
    2. 
  
  
  
  
  2. class Solution { 
    3. 
  
  
  
  
  3.     public List preorderTraversal(TreeNode root) { 
    4. 
  
  
  
  
  4.         List result = new ArrayList<>(); 
    5. 
  
  
  
  
  5.         if (root == null){ 
    6. 
  
  
  
  
  6.             return result; 
    7. 
  
  
  
  
  7.         } 
    8. 
  
  
  
  
  8.         Stack stack = new Stack<>(); 
    9. 
  
  
  
  
  9.         stack.push(root); 
    10. 
  
  
  
  
  10.         while (!stack.isEmpty()){ 
    11. 
  
  
  
  
  11.             TreeNode node = stack.pop(); 
    12. 
  
  
  
  
  12.             result.add(node.val); 
    13. 
  
  
  
  
  13.             if (node.right != null){ 
    14. 
  
  
  
  
  14.                 stack.push(node.right); 
    15. 
  
  
  
  
  15.             } 
    16. 
  
  
  
  
  16.             if (node.left != null){ 
    17. 
  
  
  
  
  17.                 stack.push(node.left); 
    18. 
  
  
  
  
  18.             } 
    19. 
  
  
  
  
  19.         } 
    20. 
  
  
  
  
  20.         return result; 
    21. 
  
  
  
  
  21.     } 
    22. 
  
  
  
  
  22. } 
    23. 
  
  
  
  
  23.  
    24. 
  
  
  
  
  24. // 中序遍歷順序: 左-中-右 入棧順序： 左-右 
    25. 
  
  
  
  
  25. class Solution { 
    26. 
  
  
  
  
  26.     public List inorderTraversal(TreeNode root) { 
    27. 
  
  
  
  
  27.         List result = new ArrayList<>(); 
    28. 
  
  
  
  
  28.         if (root == null){ 
    29. 
  
  
  
  
  29.             return result; 
    30. 
  
  
  
  
  30.         } 
    31. 
  
  
  
  
  31.         Stack stack = new Stack<>(); 
    32. 
  
  
  
  
  32.         TreeNode cur = root; 
    33. 
  
  
  
  
  33.         while (cur != null || !stack.isEmpty()){ 
    34. 
  
  
  
  
  34.            if (cur != null){ 
    35. 
  
  
  
  
  35.                stack.push(cur); 
    36. 
  
  
  
  
  36.                cur = cur.left; 
    37. 
  
  
  
  
  37.            }else{ 
    38. 
  
  
  
  
  38.                cur = stack.pop(); 
    39. 
  
  
  
  
  39.                result.add(cur.val); 
    40. 
  
  
  
  
  40.                cur = cur.right; 
    41. 
  
  
  
  
  41.            } 
    42. 
  
  
  
  
  42.         } 
    43. 
  
  
  
  
  43.         return result; 
    44. 
  
  
  
  
  44.     } 
    45. 
  
  
  
  
  45. } 
    46. 
  
  
  
  
  46.  
    47. 
  
  
  
  
  47. // 后序遍歷順序 左-右-中 入棧順序：中-左-右 出棧順序：中-右-左， 最后翻轉(zhuǎn)結(jié)果 
    48. 
  
  
  
  
  48. class Solution { 
    49. 
  
  
  
  
  49.     public List postorderTraversal(TreeNode root) { 
    50. 
  
  
  
  
  50.         List result = new ArrayList<>(); 
    51. 
  
  
  
  
  51.         if (root == null){ 
    52. 
  
  
  
  
  52.             return result; 
    53. 
  
  
  
  
  53.         } 
    54. 
  
  
  
  
  54.         Stack stack = new Stack<>(); 
    55. 
  
  
  
  
  55.         stack.push(root); 
    56. 
  
  
  
  
  56.         while (!stack.isEmpty()){ 
    57. 
  
  
  
  
  57.             TreeNode node = stack.pop(); 
    58. 
  
  
  
  
  58.             result.add(node.val); 
    59. 
  
  
  
  
  59.             if (node.left != null){ 
    60. 
  
  
  
  
  60.                 stack.push(node.left); 
    61. 
  
  
  
  
  61.             } 
    62. 
  
  
  
  
  62.             if (node.right != null){ 
    63. 
  
  
  
  
  63.                 stack.push(node.right); 
    64. 
  
  
  
  
  64.             } 
    65. 
  
  
  
  
  65.         } 
    66. 
  
  
  
  
  66.         Collections.reverse(result); 
    67. 
  
  
  
  
  67.         return result; 
    68. 
  
  
  
  
  68.     } 
    69. 
  
  
  
  
  69. } 
    70.

Python：

 
 
 
 
    
  
  
  
  
  1. # 前序遍歷-迭代-LC144_二叉樹的前序遍歷 
    2. 
  
  
  
  
  2. class Solution: 
    3. 
  
  
  
  
  3.     def preorderTraversal(self, root: TreeNode) -> List[int]: 
    4. 
  
  
  
  
  4.         # 根結(jié)點(diǎn)為空則返回空列表 
    5. 
  
  
  
  
  5.         if not root: 
    6. 
  
  
  
  
  6.             return [] 
    7. 
  
  
  
  
  7.         stack = [root] 
    8. 
  
  
  
  
  8.         result = [] 
    9. 
  
  
  
  
  9.         while stack: 
    10. 
  
  
  
  
  10.             node = stack.pop() 
    11. 
  
  
  
  
  11.             # 中結(jié)點(diǎn)先處理 
    12. 
  
  
  
  
  12.             result.append(node.val) 
    13. 
  
  
  
  
  13.             # 右孩子先入棧 
    14. 
  
  
  
  
  14.             if node.right: 
    15. 
  
  
  
  
  15.                 stack.append(node.right) 
    16. 
  
  
  
  
  16.             # 左孩子后入棧 
    17. 
  
  
  
  
  17.             if node.left: 
    18. 
  
  
  
  
  18.                 stack.append(node.left) 
    19. 
  
  
  
  
  19.         return result 
    20. 
  
  
  
  
  20.          
    21. 
  
  
  
  
  21. # 中序遍歷-迭代-LC94_二叉樹的中序遍歷 
    22. 
  
  
  
  
  22. class Solution: 
    23. 
  
  
  
  
  23.     def inorderTraversal(self, root: TreeNode) -> List[int]: 
    24. 
  
  
  
  
  24.         if not root: 
    25. 
  
  
  
  
  25.             return [] 
    26. 
  
  
  
  
  26.         stack = []  # 不能提前將root結(jié)點(diǎn)加入stack中 
    27. 
  
  
  
  
  27.         result = [] 
    28. 
  
  
  
  
  28.         cur = root 
    29. 
  
  
  
  
  29.         while cur or stack: 
    30. 
  
  
  
  
  30.             # 先迭代訪問最底層的左子樹結(jié)點(diǎn) 
    31. 
  
  
  
  
  31.             if cur:      
    32. 
  
  
  
  
  32.                 stack.append(cur) 
    33. 
  
  
  
  
  33.                 cur = cur.left   
    34. 
  
  
  
  
  34.             # 到達(dá)最左結(jié)點(diǎn)后處理?xiàng)ｍ斀Y(jié)點(diǎn)     
    35. 
  
  
  
  
  35.             else:   
    36. 
  
  
  
  
  36.                 cur = stack.pop() 
    37. 
  
  
  
  
  37.                 result.append(cur.val) 
    38. 
  
  
  
  
  38.                 # 取棧頂元素右結(jié)點(diǎn) 
    39. 
  
  
  
  
  39.                 cur = cur.right  
    40. 
  
  
  
  
  40.         return result 
    41. 
  
  
  
  
  41.          
    42. 
  
  
  
  
  42. # 后序遍歷-迭代-LC145_二叉樹的后序遍歷 
    43. 
  
  
  
  
  43. class Solution: 
    44. 
  
  
  
  
  44.     def postorderTraversal(self, root: TreeNode) -> List[int]: 
    45. 
  
  
  
  
  45.         if not root: 
    46. 
  
  
  
  
  46.             return [] 
    47. 
  
  
  
  
  47.         stack = [root] 
    48. 
  
  
  
  
  48.         result = [] 
    49. 
  
  
  
  
  49.         while stack: 
    50. 
  
  
  
  
  50.             node = stack.pop() 
    51. 
  
  
  
  
  51.             # 中結(jié)點(diǎn)先處理 
    52. 
  
  
  
  
  52.             result.append(node.val) 
    53. 
  
  
  
  
  53.             # 左孩子先入棧 
    54. 
  
  
  
  
  54.             if node.left: 
    55. 
  
  
  
  
  55.                 stack.append(node.left) 
    56. 
  
  
  
  
  56.             # 右孩子后入棧 
    57. 
  
  
  
  
  57.             if node.right: 
    58. 
  
  
  
  
  58.                 stack.append(node.right) 
    59. 
  
  
  
  
  59.         # 將最終的數(shù)組翻轉(zhuǎn) 
    60. 
  
  
  
  
  60.         return result[::-1] 
    61.

當(dāng)前名稱：聽說(shuō)遞歸能做的，棧也能做！
URL標(biāo)題：http://www.5511xx.com/article/cdidodc.html