力扣刷题 二叉树的迭代遍历

题干

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

解题思路

我们上次使用了递归来完成前中后序遍历，这次我们用迭代法来实现。

前序遍历

大体思路是用栈来实现遍历。我们先建立一个栈，把根节点root压入栈。

我们模拟从根节点root开始，先设置一个循环，当栈不为空的时候，对每一个栈顶元素循环操作。因此根节点只是一个个例，后面在写代码的时候不能只考虑根节点的情形。

我们先把root从栈中弹出，如果它不为空，则将其放入结果数组中。如果为空的话，就跳出本次循环，对下一个栈元素进行操作。（根节点是第一个栈元素，自然不会有下一个栈元素，但是我们写代码考虑的是全局情况）

然后依次把它的右子树和左子树压入栈中，因为栈是后进先出的，所以下一个出栈的就是左子树，符合中左右的顺序。

//迭代法
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {//建立一个栈stack<TreeNode*> st;//建立一个数组保存遍历结果vector<int> result;//将根节点入栈st.push(root); // 在栈不为空的情况下，重复以下操作while(!st.empty()){//将栈顶元素弹出TreeNode* node = st.top();st.pop();//当根节点不为空if(node != NULL){// 将栈顶元素放入结果数组result.push_back(node->val);}//若为空, 则忽略这个节点，去访问下一个节点else{continue;}//将节点的右子树的根节点放入栈st.push(node->right);//将节点的左子树的根节点放入栈，这样下一个遍历的就是左子树st.push(node->left); }// 返回遍历的结果return result;}
};

写完了前序遍历的迭代法遍历，后序遍历就可以轻松写出了，因为前序遍历的顺序是中左右，而后序遍历是左右中。想要从前序变为后序，只需先将左右调换位置，变成中右左，再翻转数组就实现左右中了。而左右调换位置和简单，只需将入栈的顺序调换即可。而翻转函数之前我们也接触过。

后序遍历代码如下

这里我稍微修改了写法，把根节点root和普通根节点的情况做了区分，可能更容易理解，但本质相同。

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();st.pop();result.push_back(node->val);if (node->left)st.push(node->left);if (node->right)st.push(node->right);}reverse(result.begin(), result.end());return result;}
};

而中序遍历就没有那么简单了。

为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作：

1. 处理：将元素放进result数组中
2. 访问：遍历节点

分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

我们设置cur为指针，指针帮助我们一层层访问左子树，直到叶子节点。而当到叶子节点则意味着我们要在做处理了，把根节点弹出，放入结果数组，再访问根节点的右子树，继续层层访问左子树，直到叶子节点。

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;//用指针来访问元素TreeNode* cur = root;//当栈不为空, 当前根节点不为空时，循环以下操作while( cur != NULL||!st.empty()){// 如果指针不为空if(cur != NULL){st.push(cur);cur = cur->left;}//指针为空，说明要开始处理元素，则弹出栈顶else{//弹出根节点cur = st.top();st.pop();//放入结果数组result.push_back(cur->val);//访问根节点的右子树cur = cur->right;}  }return result;}
};

while(cur !=NULL||!st.empty()){

 这段代码是循环结束的条件，注意当cur指向根节点root，栈那是还是空的，所以要加一个cur不是空的条件。