题干
给你二叉树的根节点 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;
}
};而中序遍历就没有那么简单了。
为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作：
- 处理：将元素放进result数组中
- 访问：遍历节点
分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进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不是空的条件。
