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

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

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
一個(gè)套路，寫出來二叉樹的迭代遍歷

二叉樹的統(tǒng)一迭代法

此時(shí)我們在二叉樹：一入遞歸深似海，從此offer是路人中用遞歸的方式，實(shí)現(xiàn)了二叉樹前中后序的遍歷。

在二叉樹：聽說遞歸能做的，棧也能做!中用棧實(shí)現(xiàn)了二叉樹前后中序的迭代遍歷(非遞歸)。

之后我們發(fā)現(xiàn)迭代法實(shí)現(xiàn)的先中后序，其實(shí)風(fēng)格也不是那么統(tǒng)一，除了先序和后序，有關(guān)聯(lián)，中序完全就是另一個(gè)風(fēng)格了，一會(huì)用棧遍歷，一會(huì)又用指針來遍歷。

實(shí)踐過的同學(xué)，也會(huì)發(fā)現(xiàn)使用迭代法實(shí)現(xiàn)先中后序遍歷，很難寫出統(tǒng)一的代碼，不像是遞歸法，實(shí)現(xiàn)了其中的一種遍歷方式，其他兩種只要稍稍改一下節(jié)點(diǎn)順序就可以了。

其實(shí)針對三種遍歷方式，使用迭代法是可以寫出統(tǒng)一風(fēng)格的代碼!

重頭戲來了，接下來介紹一下統(tǒng)一寫法。

我們以中序遍歷為例，在二叉樹：聽說遞歸能做的，棧也能做!中提到說使用棧的話，無法同時(shí)解決訪問節(jié)點(diǎn)(遍歷節(jié)點(diǎn))和處理節(jié)點(diǎn)(將元素放進(jìn)結(jié)果集)不一致的情況。

那我們就將訪問的節(jié)點(diǎn)放入棧中，把要處理的節(jié)點(diǎn)也放入棧中但是要做標(biāo)記。

如何標(biāo)記呢，就是要處理的節(jié)點(diǎn)放入棧之后，緊接著放入一個(gè)空指針作為標(biāo)記。 這種方法也可以叫做標(biāo)記法。

迭代法中序遍歷

中序遍歷代碼如下：(詳細(xì)注釋)

  
 
 
 
    
   
  
  
  
  1. class Solution {
    2. 
   
  
  
  
  2. public:
    3. 
   
  
  
  
  3.     vector inorderTraversal(TreeNode* root) {
    4. 
   
  
  
  
  4.         vector result;
    5. 
   
  
  
  
  5.         stack st;
    6. 
   
  
  
  
  6.         if (root != NULL) st.push(root);
    7. 
   
  
  
  
  7.         while (!st.empty()) {
    8. 
   
  
  
  
  8.             TreeNode* node = st.top();
    9. 
   
  
  
  
  9.             if (node != NULL) {
    10. 
   
  
  
  
  10.                 st.pop(); // 將該節(jié)點(diǎn)彈出，避免重復(fù)操作，下面再將右中左節(jié)點(diǎn)添加到棧中
    11. 
   
  
  
  
  11.                 if (node->right) st.push(node->right);  // 添加右節(jié)點(diǎn)（空節(jié)點(diǎn)不入棧）
    12. 
   
  
  
  
  12. 
   
  
  
  
  13.                 st.push(node);                          // 添加中節(jié)點(diǎn)
    14. 
   
  
  
  
  14.                 st.push(NULL); // 中節(jié)點(diǎn)訪問過，但是還沒有處理，加入空節(jié)點(diǎn)做為標(biāo)記。
    15. 
   
  
  
  
  15. 
   
  
  
  
  16.                 if (node->left) st.push(node->left);    // 添加左節(jié)點(diǎn)（空節(jié)點(diǎn)不入棧）
    17. 
   
  
  
  
  17.             } else { // 只有遇到空節(jié)點(diǎn)的時(shí)候，才將下一個(gè)節(jié)點(diǎn)放進(jìn)結(jié)果集
    18. 
   
  
  
  
  18.                 st.pop();           // 將空節(jié)點(diǎn)彈出
    19. 
   
  
  
  
  19.                 node = st.top();    // 重新取出棧中元素
    20. 
   
  
  
  
  20.                 st.pop();
    21. 
   
  
  
  
  21.                 result.push_back(node->val); // 加入到結(jié)果集
    22. 
   
  
  
  
  22.             }
    23. 
   
  
  
  
  23.         }
    24. 
   
  
  
  
  24.         return result;
    25. 
   
  
  
  
  25.     }
    26. 
   
  
  
  
  26. };
    27.

看代碼有點(diǎn)抽象我們來看一下動(dòng)畫(中序遍歷)：

中序遍歷迭代(統(tǒng)一寫法)

動(dòng)畫中，result數(shù)組就是最終結(jié)果集。

可以看出我們將訪問的節(jié)點(diǎn)直接加入到棧中，但如果是處理的節(jié)點(diǎn)則后面放入一個(gè)空節(jié)點(diǎn)， 這樣只有空節(jié)點(diǎn)彈出的時(shí)候，才將下一個(gè)節(jié)點(diǎn)放進(jìn)結(jié)果集。

此時(shí)我們再來看前序遍歷代碼。

迭代法前序遍歷

迭代法前序遍歷代碼如下：(注意此時(shí)我們和中序遍歷相比僅僅改變了兩行代碼的順序)

  
 
 
 
    
   
  
  
  
  1. class Solution {
    2. 
   
  
  
  
  2. public:
    3. 
   
  
  
  
  3.     vector preorderTraversal(TreeNode* root) {
    4. 
   
  
  
  
  4.         vector result;
    5. 
   
  
  
  
  5.         stack st;
    6. 
   
  
  
  
  6.         if (root != NULL) st.push(root);
    7. 
   
  
  
  
  7.         while (!st.empty()) {
    8. 
   
  
  
  
  8.             TreeNode* node = st.top();
    9. 
   
  
  
  
  9.             if (node != NULL) {
    10. 
   
  
  
  
  10.                 st.pop();
    11. 
   
  
  
  
  11.                 if (node->right) st.push(node->right);  // 右
    12. 
   
  
  
  
  12.                 if (node->left) st.push(node->left);    // 左
    13. 
   
  
  
  
  13.                 st.push(node);                          // 中
    14. 
   
  
  
  
  14.                 st.push(NULL);
    15. 
   
  
  
  
  15.             } else {
    16. 
   
  
  
  
  16.                 st.pop();
    17. 
   
  
  
  
  17.                 node = st.top();
    18. 
   
  
  
  
  18.                 st.pop();
    19. 
   
  
  
  
  19.                 result.push_back(node->val);
    20. 
   
  
  
  
  20.             }
    21. 
   
  
  
  
  21.         }
    22. 
   
  
  
  
  22.         return result;
    23. 
   
  
  
  
  23.     }
    24. 
   
  
  
  
  24. };
    25.

迭代法后序遍歷

后續(xù)遍歷代碼如下：(注意此時(shí)我們和中序遍歷相比僅僅改變了兩行代碼的順序)

  
 
 
 
    
   
  
  
  
  1. class Solution {
    2. 
   
  
  
  
  2. public:
    3. 
   
  
  
  
  3.     vector postorderTraversal(TreeNode* root) {
    4. 
   
  
  
  
  4.         vector result;
    5. 
   
  
  
  
  5.         stack st;
    6. 
   
  
  
  
  6.         if (root != NULL) st.push(root);
    7. 
   
  
  
  
  7.         while (!st.empty()) {
    8. 
   
  
  
  
  8.             TreeNode* node = st.top();
    9. 
   
  
  
  
  9.             if (node != NULL) {
    10. 
   
  
  
  
  10.                 st.pop();
    11. 
   
  
  
  
  11.                 st.push(node);                          // 中
    12. 
   
  
  
  
  12.                 st.push(NULL);
    13. 
   
  
  
  
  13. 
   
  
  
  
  14.                 if (node->right) st.push(node->right);  // 右
    15. 
   
  
  
  
  15.                 if (node->left) st.push(node->left);    // 左
    16. 
   
  
  
  
  16. 
   
  
  
  
  17.             } else {
    18. 
   
  
  
  
  18.                 st.pop();
    19. 
   
  
  
  
  19.                 node = st.top();
    20. 
   
  
  
  
  20.                 st.pop();
    21. 
   
  
  
  
  21.                 result.push_back(node->val);
    22. 
   
  
  
  
  22.             }
    23. 
   
  
  
  
  23.         }
    24. 
   
  
  
  
  24.         return result;
    25. 
   
  
  
  
  25.     }
    26. 
   
  
  
  
  26. };
    27.

總結(jié)

此時(shí)我們寫出了統(tǒng)一風(fēng)格的迭代法，不用在糾結(jié)于前序?qū)懗鰜砹?，中序?qū)懖怀鰜淼那闆r了。

但是統(tǒng)一風(fēng)格的迭代法并不好理解，而且想在面試直接寫出來還有難度的。

所以大家根據(jù)自己的個(gè)人喜好，對于二叉樹的前中后序遍歷，選擇一種自己容易理解的遞歸和迭代法。

其他語言版本

Java：迭代法前序遍歷代碼如下:

  
 
 
 
    
   
  
  
  
  1. class Solution {
    2. 
   
  
  
  
  2.     public List preorderTraversal(TreeNode root) {
    3. 
   
  
  
  
  3.         List result = new LinkedList<>();
    4. 
   
  
  
  
  4.         Stack st = new Stack<>();
    5. 
   
  
  
  
  5.         if (root != null) st.push(root);
    6. 
   
  
  
  
  6.         while (!st.empty()) {
    7. 
   
  
  
  
  7.             TreeNode node = st.peek();
    8. 
   
  
  
  
  8.             if (node != null) {
    9. 
   
  
  
  
  9.                 st.pop(); // 將該節(jié)點(diǎn)彈出，避免重復(fù)操作，下面再將右中左節(jié)點(diǎn)添加到棧中
    10. 
   
  
  
  
  10.                 if (node.right!=null) st.push(node.right);  // 添加右節(jié)點(diǎn)（空節(jié)點(diǎn)不入棧）
    11. 
   
  
  
  
  11.                 if (node.left!=null) st.push(node.left);    // 添加左節(jié)點(diǎn)（空節(jié)點(diǎn)不入棧）
    12. 
   
  
  
  
  12.                 st.push(node);                          // 添加中節(jié)點(diǎn)
    13. 
   
  
  
  
  13.                 st.push(null); // 中節(jié)點(diǎn)訪問過，但是還沒有處理，加入空節(jié)點(diǎn)做為標(biāo)記。
    14. 
   
  
  
  
  14.                 
    15. 
   
  
  
  
  15.             } else { // 只有遇到空節(jié)點(diǎn)的時(shí)候，才將下一個(gè)節(jié)點(diǎn)放進(jìn)結(jié)果集
    16. 
   
  
  
  
  16.                 st.pop();           // 將空節(jié)點(diǎn)彈出
    17. 
   
  
  
  
  17.                 node = st.peek();    // 重新取出棧中元素
    18. 
   
  
  
  
  18.                 st.pop();
    19. 
   
  
  
  
  19.                 result.add(node.val); // 加入到結(jié)果集
    20. 
   
  
  
  
  20.             }
    21. 
   
  
  
  
  21.         }
    22. 
   
  
  
  
  22.         return result;
    23. 
   
  
  
  
  23.     }
    24. 
   
  
  
  
  24. }
    25.

迭代法中序遍歷代碼如下:

  
 
 
 
    
   
  
  
  
  1. class Solution {
    2. 
   
  
  
  
  2. public List inorderTraversal(TreeNode root) {
    3. 
   
  
  
  
  3.         List result = new LinkedList<>();
    4. 
   
  
  
  
  4.     Stack st = new Stack<>();
    5. 
   
  
  
  
  5.     if (root != null) st.push(root);
    6. 
   
  
  
  
  6.     while (!st.empty()) {
    7. 
   
  
  
  
  7.         TreeNode node = st.peek();
    8. 
   
  
  
  
  8.         if (node != null) {
    9. 
   
  
  
  
  9.             st.pop(); // 將該節(jié)點(diǎn)彈出，避免重復(fù)操作，下面再將右中左節(jié)點(diǎn)添加到棧中
    10. 
   
  
  
  
  10.             if (node.right!=null) st.push(node.right);  // 添加右節(jié)點(diǎn)（空節(jié)點(diǎn)不入棧）
    11. 
   
  
  
  
  11.             st.push(node);                          // 添加中節(jié)點(diǎn)
    12. 
   
  
  
  
  12.             st.push(null); // 中節(jié)點(diǎn)訪問過，但是還沒有處理，加入空節(jié)點(diǎn)做為標(biāo)記。
    13. 
   
  
  
  
  13. 
   
  
  
  
  14.             if (node.left!=null) st.push(node.left);    // 添加左節(jié)點(diǎn)（空節(jié)點(diǎn)不入棧）
    15. 
   
  
  
  
  15.         } else { // 只有遇到空節(jié)點(diǎn)的時(shí)候，才將下一個(gè)節(jié)點(diǎn)放進(jìn)結(jié)果集
    16. 
   
  
  
  
  16.             st.pop();           // 將空節(jié)點(diǎn)彈出
    17. 
   
  
  
  
  17.             node = st.peek();    // 重新取出棧中元素
    18. 
   
  
  
  
  18.             st.pop();
    19. 
   
  
  
  
  19.             result.add(node.val); // 加入到結(jié)果集
    20. 
   
  
  
  
  20.         }
    21. 
   
  
  
  
  21.     }
    22. 
   
  
  
  
  22.     return result;
    23. 
   
  
  
  
  23. }
    24. 
   
  
  
  
  24. }
    25.

迭代法后序遍歷代碼如下:

  
 
 
 
    
   
  
  
  
  1. class Solution {
    2. 
   
  
  
  
  2.    public List postorderTraversal(TreeNode root) {
    3. 
   
  
  
  
  3.         List result = new LinkedList<>();
    4. 
   
  
  
  
  4.         Stack st = new Stack<>();
    5. 
   
  
  
  
  5.         if (root != null) st.push(root);
    6. 
   
  
  
  
  6.         while (!st.empty()) {
    7. 
   
  
  
  
  7.             TreeNode node = st.peek();
    8. 
   
  
  
  
  8.             if (node != null) {
    9. 
   
  
  
  
  9.                 st.pop(); // 將該節(jié)點(diǎn)彈出，避免重復(fù)操作，下面再將右中左節(jié)點(diǎn)添加到棧中
    10. 
   
  
  
  
  10.                 st.push(node);                          // 添加中節(jié)點(diǎn)
    11. 
   
  
  
  
  11.                 st.push(null); // 中節(jié)點(diǎn)訪問過，但是還沒有處理，加入空節(jié)點(diǎn)做為標(biāo)記。
    12. 
   
  
  
  
  12.                 if (node.right!=null) st.push(node.right);  // 添加右節(jié)點(diǎn)（空節(jié)點(diǎn)不入棧）
    13. 
   
  
  
  
  13.                 if (node.left!=null) st.push(node.left);    // 添加左節(jié)點(diǎn)（空節(jié)點(diǎn)不入棧）         
    14. 
   
  
  
  
  14.                                
    15. 
   
  
  
  
  15.             } else { // 只有遇到空節(jié)點(diǎn)的時(shí)候，才將下一個(gè)節(jié)點(diǎn)放進(jìn)結(jié)果集
    16. 
   
  
  
  
  16.                 st.pop();           // 將空節(jié)點(diǎn)彈出
    17. 
   
  
  
  
  17.                 node = st.peek();    // 重新取出棧中元素
    18. 
   
  
  
  
  18.                 st.pop();
    19. 
   
  
  
  
  19.                 result.add(node.val); // 加入到結(jié)果集
    20. 
   
  
  
  
  20.             }
    21. 
   
  
  
  
  21.         }
    22. 
   
  
  
  
  22.         return result;
    23. 
   
  
  
  
  23.    }
    24. 
   
  
  
  
  24. }
    25.

Python：

迭代法前序遍歷：

  
 
 
 
    
   
  
  
  
  1. class Solution:
    2. 
   
  
  
  
  2.     def preorderTraversal(self, root: TreeNode) -> List[int]:
    3. 
   
  
  
  
  3.         result = []
    4. 
   
  
  
  
  4.         st= []
    5. 
   
  
  
  
  5.         if root:
    6. 
   
  
  
  
  6.             st.append(root)
    7. 
   
  
  
  
  7.         while st:
    8. 
   
  
  
  
  8.             node = st.pop()
    9. 
   
  
  
  
  9.             if node != None:
    10. 
   
  
  
  
  10.                 if node.right: #右
    11. 
   
  
  
  
  11.                     st.append(node.right)
    12. 
   
  
  
  
  12.                 if node.left: #左
    13. 
   
  
  
  
  13.                     st.append(node.left)
    14. 
   
  
  
  
  14.                 st.append(node) #中
    15. 
   
  
  
  
  15.                 st.append(None)
    16. 
   
  
  
  
  16.             else:
    17. 
   
  
  
  
  17.                 node = st.pop()
    18. 
   
  
  
  
  18.                 result.append(node.val)
    19. 
   
  
  
  
  19.         return result
    20.

迭代法中序遍歷：

  
 
 
 
    
   
  
  
  
  1. class Solution:
    2. 
   
  
  
  
  2.     def inorderTraversal(self, root: TreeNode) -> List[int]:
    3. 
   
  
  
  
  3.         result = []
    4. 
   
  
  
  
  4.         st = []
    5. 
   
  
  
  
  5.         if root:
    6. 
   
  
  
  
  6.             st.append(root)
    7. 
   
  
  
  
  7.         while st:
    8. 
   
  
  
  
  8.             node = st.pop()
    9. 
   
  
  
  
  9.             if node != None:
    10. 
   
  
  
  
  10.                 if node.right: #添加右節(jié)點(diǎn)（空節(jié)點(diǎn)不入棧）
    11. 
   
  
  
  
  11.                     st.append(node.right)
    12. 
   
  
  
  
  12.                 
    13. 
   
  
  
  
  13.                 st.append(node) #添加中節(jié)點(diǎn)
    14. 
   
  
  
  
  14.                 st.append(None) #中節(jié)點(diǎn)訪問過，但是還沒有處理，加入空節(jié)點(diǎn)做為標(biāo)記。
    15. 
   
  
  
  
  15.                 
    16. 
   
  
  
  
  16.                 if node.left: #添加左節(jié)點(diǎn)（空節(jié)點(diǎn)不入棧）
    17. 
   
  
  
  
  17.                     st.append(node.left)
    18. 
   
  
  
  
  18.             else: #只有遇到空節(jié)點(diǎn)的時(shí)候，才將下一個(gè)節(jié)點(diǎn)放進(jìn)結(jié)果集
    19. 
   
  
  
  
  19.                 node = st.pop() #重新取出棧中元素
    20. 
   
  
  
  
  20.                 result.append(node.val) #加入到結(jié)果集
    21. 
   
  
  
  
  21.         return result
    22.

迭代法后序遍歷：

  
 
 
 
    
   
  
  
  
  1. class Solution:
    2. 
   
  
  
  
  2.     def postorderTraversal(self, root: TreeNode) -> List[int]:
    3. 
   
  
  
  
  3.         result = []
    4. 
   
  
  
  
  4.         st = []
    5. 
   
  
  
  
  5.         if root:
    6. 
   
  
  
  
  6.             st.append(root)
    7. 
   
  
  
  
  7.         while st:
    8. 
   
  
  
  
  8.             node = st.pop()
    9. 
   
  
  
  
  9.             if node != None:
    10. 
   
  
  
  
  10.                 st.append(node) #中
    11. 
   
  
  
  
  11.                 st.append(None)
    12. 
   
  
  
  
  12.                 
    13. 
   
  
  
  
  13.                 if node.right: #右
    14. 
   
  
  
  
  14.                     st.append(node.right)
    15. 
   
  
  
  
  15.                 if node.left: #左
    16. 
   
  
  
  
  16.                     st.append(node.left)
    17. 
   
  
  
  
  17.             else:
    18. 
   
  
  
  
  18.                 node = st.pop()
    19. 
   
  
  
  
  19.                 result.append(node.val)
    20. 
   
  
  
  
  20.         return result
    21.

舊文鏈接：二叉樹：前中后序迭代方式的寫法就不能統(tǒng)一一下么?


新聞標(biāo)題：一個(gè)套路，寫出來二叉樹的迭代遍歷
鏈接分享：http://www.5511xx.com/article/dhcscoo.html