一.相关链接
题目链接：
二.心得体会
前面用简单的递归法几行实现了这些问题，有些题目可以用迭代法来实现，通常使用的辅助数据结构是栈（递归的底层逻辑就是栈）。
1.对于前序遍历来说，整体的方法比较简单，在弹出节点的时候，只需要把该节点的右节点和左节点依次弹进栈即可（因为栈是先进后出）。
2.后序遍历相对来说比较简单，目前知道前序遍历是中左右，那么我们改变左右子树的遍历顺序就成了中右左，然后整体翻转就变成了后序遍历的左右中了！
3.对于中序遍历来说，因为它的遍历顺序和访问顺序不一样，所以和前序、中序不一样。那么我们就要首先一路往最左下角找到第一个节点。一直到访问到空节点的时候，代表我们找到了最左边的节点，那么就可以开始访问这个节点，并回溯到它的父节点访问父节点，接下来就是往右子树访问了。
三.代码
1.前序遍历的迭代法实现：
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
if(root!=NULL) st.push(root);
while(!st.empty()) {
TreeNode* node = st.top();
st.pop();
ans.push_back(node->val);
if(node->right!=NULL) st.push(node->right);
if(node->left!=NULL) st.push(node->left);
}
return ans;
}
};2.后续遍历的迭代法实现：
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
if(root!=NULL) st.push(root);
while(!st.empty()) {
TreeNode* node = st.top();
st.pop();
ans.push_back(node->val);
if(node->left) st.push(node->left);
if(node->right) st.push(node->right);
}
reverse(ans.begin(), ans.end());
return ans;
}
};3.中序遍历的迭代法实现：
class Solution {
public:
vector<int> ans;
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* node = root;
while(node!=NULL||!st.empty()) {
if(node!=NULL) {
st.push(node);
node = node->left;
}
else {
node = st.top();
st.pop();
ans.push_back(node->val);
node = node->right;
}
}
return ans;
}
};