6.2二叉树的迭代遍历

6.2二叉树的迭代遍历

6.2二叉树的迭代遍历

文章目录

​​6.2二叉树的迭代遍历​​​​一、使用迭代法实现中序遍历​​​​二、使用迭代法实现前序遍历​​​​三、使用迭代法实现后序遍历​​

在6.1中我们通过使用递归实现了二叉树的前、中、后序的遍历，本文将介绍使用迭代法实现二叉树前中后遍历，写出统一风格的代码。

根本思想：将要访问的节点放入栈中，将要处理的节点放入栈中但是要做标记，即将要处理的节点放入栈中以后，紧接着放入一个空指针作为标记。这种方法也可以叫 标记法。

一、使用迭代法实现中序遍历

class Solution {public: vector inorderTraversal(TreeNode* root) { vector result; stack st; if (root != NULL) st.push(root); while (!st.empty()) { TreeNode* node = st-(); if (node != NULL) { st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中 if (node->right) st.push(node->right); // 添加右节点（空节点不入栈） st.push(node); // 添加中节点 st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。 if (node->left) st.push(node->left); // 添加左节点（空节点不入栈） } else { // 只有遇到空节点的时候，才将下一个节点放进结果集 st.pop(); // 将空节点弹出 node = st-(); // 重新取出栈中元素 st.pop(); result.push_back(node->val); // 加入到结果集 } } return result; }};

二、使用迭代法实现前序遍历

理论：中-左-右

代码：右-左-中

在中序遍历的基础上改变三行代码即可。

class Solution {public: vector preorderTraversal(TreeNode* root) { vector result; stack st; if (root != NULL) st.push(root); while (!st.empty()) { TreeNode* node = st-(); if (node != NULL) { st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中 if (node->right) st.push(node->right); // 添加右节点（空节点不入栈） if (node->left) st.push(node->left); // 添加左节点（空节点不入栈） st.push(node); // 添加中节点 st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。 } else { // 只有遇到空节点的时候，才将下一个节点放进结果集 st.pop(); // 将空节点弹出 node = st-(); // 重新取出栈中元素 st.pop(); result.push_back(node->val); // 加入到结果集 } } return result; }};

三、使用迭代法实现后序遍历

在中序遍历的基础上改变三行代码即可。

理论：左-右-中

代码：中-右-左

class Solution {public: vector postorderTraversal(TreeNode* root) { vector result; stack st; if (root != NULL) st.push(root); while (!st.empty()) { TreeNode* node = st-(); if (node != NULL) { st.pop(); st.push(node); // 中 st.push(NULL); if (node->right) st.push(node->right); // 右 if (node->left) st.push(node->left); // 左 } else { st.pop(); node = st-(); st.pop(); result.push_back(node->val); } } return result; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。