一个套路，写出来二叉树的迭代遍历

二叉树的统一迭代法

此时我们在二叉树：一入递归深似海，从此offer是路人中用递归的方式，实现了二叉树前中后序的遍历。

在二叉树：听说递归能做的，栈也能做!中用栈实现了二叉树前后中序的迭代遍历(非递归)。

之后我们发现迭代法实现的先中后序，其实风格也不是那么统一，除了先序和后序，有关联，中序完全就是另一个风格了，一会用栈遍历，一会又用指针来遍历。

实践过的同学，也会发现使用迭代法实现先中后序遍历，很难写出统一的代码，不像是递归法，实现了其中的一种遍历方式，其他两种只要稍稍改一下节点顺序就可以了。

其实针对三种遍历方式，使用迭代法是可以写出统一风格的代码!

重头戏来了，接下来介绍一下统一写法。

我们以中序遍历为例，在二叉树：听说递归能做的，栈也能做!中提到说使用栈的话，无法同时解决访问节点(遍历节点)和处理节点(将元素放进结果集)不一致的情况。

那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。

如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

迭代法中序遍历

中序遍历代码如下：(详细注释)

  
 
 
 
    
   
  
  
  
  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(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
    11. 
   
  
  
  
  11.                 if (node->right) st.push(node->right);  // 添加右节点（空节点不入栈）
    12. 
   
  
  
  
  12. 
   
  
  
  
  13.                 st.push(node);                          // 添加中节点
    14. 
   
  
  
  
  14.                 st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。
    15. 
   
  
  
  
  15. 
   
  
  
  
  16.                 if (node->left) st.push(node->left);    // 添加左节点（空节点不入栈）
    17. 
   
  
  
  
  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.

看代码有点抽象我们来看一下动画(中序遍历)：

中序遍历迭代(统一写法)

动画中，result数组就是最终结果集。

可以看出我们将访问的节点直接加入到栈中，但如果是处理的节点则后面放入一个空节点， 这样只有空节点弹出的时候，才将下一个节点放进结果集。

此时我们再来看前序遍历代码。

迭代法前序遍历

迭代法前序遍历代码如下：(注意此时我们和中序遍历相比仅仅改变了两行代码的顺序)

  
 
 
 
    
   
  
  
  
  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.

迭代法后序遍历

后续遍历代码如下：(注意此时我们和中序遍历相比仅仅改变了两行代码的顺序)

  
 
 
 
    
   
  
  
  
  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.

总结

此时我们写出了统一风格的迭代法，不用在纠结于前序写出来了，中序写不出来的情况了。

但是统一风格的迭代法并不好理解，而且想在面试直接写出来还有难度的。

所以大家根据自己的个人喜好，对于二叉树的前中后序遍历，选择一种自己容易理解的递归和迭代法。

其他语言版本

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(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
    10. 
   
  
  
  
  10.                 if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
    11. 
   
  
  
  
  11.                 if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
    12. 
   
  
  
  
  12.                 st.push(node);                          // 添加中节点
    13. 
   
  
  
  
  13.                 st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
    14. 
   
  
  
  
  14.                 
    15. 
   
  
  
  
  15.             } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
    16. 
   
  
  
  
  16.                 st.pop();           // 将空节点弹出
    17. 
   
  
  
  
  17.                 node = st.peek();    // 重新取出栈中元素
    18. 
   
  
  
  
  18.                 st.pop();
    19. 
   
  
  
  
  19.                 result.add(node.val); // 加入到结果集
    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(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
    10. 
   
  
  
  
  10.             if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
    11. 
   
  
  
  
  11.             st.push(node);                          // 添加中节点
    12. 
   
  
  
  
  12.             st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
    13. 
   
  
  
  
  13. 
   
  
  
  
  14.             if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
    15. 
   
  
  
  
  15.         } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
    16. 
   
  
  
  
  16.             st.pop();           // 将空节点弹出
    17. 
   
  
  
  
  17.             node = st.peek();    // 重新取出栈中元素
    18. 
   
  
  
  
  18.             st.pop();
    19. 
   
  
  
  
  19.             result.add(node.val); // 加入到结果集
    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(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
    10. 
   
  
  
  
  10.                 st.push(node);                          // 添加中节点
    11. 
   
  
  
  
  11.                 st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
    12. 
   
  
  
  
  12.                 if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
    13. 
   
  
  
  
  13.                 if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）         
    14. 
   
  
  
  
  14.                                
    15. 
   
  
  
  
  15.             } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
    16. 
   
  
  
  
  16.                 st.pop();           // 将空节点弹出
    17. 
   
  
  
  
  17.                 node = st.peek();    // 重新取出栈中元素
    18. 
   
  
  
  
  18.                 st.pop();
    19. 
   
  
  
  
  19.                 result.add(node.val); // 加入到结果集
    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: #添加右节点（空节点不入栈）
    11. 
   
  
  
  
  11.                     st.append(node.right)
    12. 
   
  
  
  
  12.                 
    13. 
   
  
  
  
  13.                 st.append(node) #添加中节点
    14. 
   
  
  
  
  14.                 st.append(None) #中节点访问过，但是还没有处理，加入空节点做为标记。
    15. 
   
  
  
  
  15.                 
    16. 
   
  
  
  
  16.                 if node.left: #添加左节点（空节点不入栈）
    17. 
   
  
  
  
  17.                     st.append(node.left)
    18. 
   
  
  
  
  18.             else: #只有遇到空节点的时候，才将下一个节点放进结果集
    19. 
   
  
  
  
  19.                 node = st.pop() #重新取出栈中元素
    20. 
   
  
  
  
  20.                 result.append(node.val) #加入到结果集
    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.

旧文链接：二叉树：前中后序迭代方式的写法就不能统一一下么?

当前文章：一个套路，写出来二叉树的迭代遍历
本文链接：http://www.shufengxianlan.com/qtweb/news47/337397.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

python知识

同城分类信息

成都微信开发　　 　成都门窗定制　　 　帝美豪门窗　　 　名片印刷　　 　成都艾瑞格　　 　阿坝网站设计　　 　成都装修公司　　 　高端网站设计　　 　达州主机托管　　 　江安网站建设　　 　绵阳网站建设　　 　网站推广营销　　 　成都工装公司　　 　装饰公司网站建设方案　　 　泸州叙永网站建设　　 　乐山网站建设　　 　三台网站建设　　 　华泰海航　　 　网络营销推广　　 　定制网站建设