# 前序的非递归

1.先访问左路节点
2.访问左路结点的同时入栈
3.子问题的方式再去访问右子树

``````/**
* 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> preorderTraversal(TreeNode* root) {
vector<int> res; //存val值
stack<TreeNode*>st;//定义一个栈

TreeNode* cur = root;//cur指向谁就开始访问谁

while(cur || !st.empty()) //当cur为空或者栈为空循环结束
{
while(cur)
{
res.push_back(cur->val);//把值存到vector
st.push(cur);   //入栈
cur=cur->left;
}

TreeNode* top = st.top();//取栈顶结点
st.pop();

//访问右子树交给子问题的方式解决
cur=top->right;
}
//最后返回vector
return res;
}
};
``````

# 中序的非递归

``````/**
* 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> res;
stack<TreeNode*>st;
TreeNode* cur = root;

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

st.push(cur);//现将结点入栈
cur=cur->left;
}

TreeNode* top = st.top();
res.push_back(top->val);//访问栈顶元素
st.pop();

cur=top->right;
}

return res;
}
};
``````

# 后序的非递归

1.左路结点入栈
2.观察栈顶结点
3.栈顶结点的右子树为空或者访问完右子树，访问栈顶结点。栈顶结点出栈，并记录栈顶结点
4.栈顶结点的右子树若没访问，则准备访问右子树

``````/**
* 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> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*>st;
TreeNode* cur = root;
TreeNode* prev = nullptr;
while(cur || !st.empty())
{
while(cur)
{
st.push(cur);//左路结点先入栈
cur = cur->left;
}
TreeNode* top = st.top();
//右子树为空，或者栈顶的右子树是根节点则可以访问根节点
if(top->right == nullptr || top->right == prev)
{
res.push_back(top->val);
st.pop();
prev = top;//记录栈顶结点
}
else
{
cur = top->right;
}
}
return res;
}
};
``````

THE END