在6.1中我们通过使用递归实现了二叉树的前、中、后序的遍历，本文将介绍使用迭代法实现二叉树前中后遍历，写出统一风格的代码。
根本思想：将要访问的节点放入栈中，将要处理的节点放入栈中但是要做标记，即将要处理的节点放入栈中以后，紧接着放入一个空指针作为标记。这种方法也可以叫 标记法。
一、使用迭代法实现中序遍历
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; if (root != NULL) st.push(root); while (!st.empty()) { TreeNode* node = st.top(); 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.top(); // 重新取出栈中元素 st.pop(); result.push_back(node->val); // 加入到结果集 } } return result; } };
二、使用迭代法实现前序遍历
理论：中-左-右
代码：右-左-中
在中序遍历的基础上改变三行代码即可。
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; if (root != NULL) st.push(root); while (!st.empty()) { TreeNode* node = st.top(); 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.top(); // 重新取出栈中元素 st.pop(); result.push_back(node->val); // 加入到结果集 } } return result; } };
三、使用迭代法实现后序遍历
在中序遍历的基础上改变三行代码即可。
理论：左-右-中
代码：中-右-左
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; if (root != NULL) st.push(root); while (!st.empty()) { TreeNode* node = st.top(); 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.top(); st.pop(); result.push_back(node->val); } } return result; } };
