二叉树前序迭代法遍历
前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。
为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
/**
1. Definition for a binary tree node.
2. struct TreeNode {
3. int val;
4. TreeNode *left;
5. TreeNode *right;
6. TreeNode() : val(0), left(nullptr), right(nullptr) {}
7. TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8. TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
9. };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if(root == nullptr) return result;
st.push(root);//根节点入栈
while(!st.empty()){
TreeNode* node = st.top();//获取栈顶元素
st.pop();//弹出
result.push_back(node->val);//加入数组中
if(node->right) st.push(node->right);//不为空，入栈
if(node->left) st.push(node->left);//不为空，入栈
}
return result;
}
};
中序遍历（迭代法）
为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作：
处理：将元素放进result数组中
访问：遍历节点
分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢?
因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
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;//更新cur
}else{
cur = st.top();
result.push_back(cur->val);//1.左元素访问到底了，加入结果;2.是中节点
st.pop();//弹出栈顶元素
cur = cur->right;更新cur为右节点，再次判断
}
}
return result;
}
};
后序遍历（迭代法）
再来看后序遍历，前序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下前序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：
前序到后序
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if (root == NULL) return result;
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数组中。
3.用栈来做存储节点的数据结构，先进后出，每次添加进result数组时，都是栈顶元素，然后pop()。
