一个总结帖，dalao们求轻喷小白。

布吉岛各位是不是和本学渣一样，一碰到非递归的二叉树遍历就感觉棘手滴不得了，刚好本渣在网上看到了一篇总结帖，

看完后直呼过瘾，原来非递归的前中后遍历和递归版本的一样简单？！

真的是相见恨晚鸭有木有，好吧，现在就用五分钟来总结一下，让你（其实是让我自己）从此以后写非递归的前中后序遍历就和写递归的一样得心应手（其实写递归版本也不得心应手）。

首先，我们知道，前序遍历是根左右的顺序，中序遍历是左根右的顺序，后序遍历是左右根的顺序。然鹅，我们只要仔细思考一下不难发现，我们可以将后续遍历看成是根右左遍历之后把数组反转即可！！

在非递归版本下的前序遍历可以以这么一种思路实现，初始化一个栈，让我们的根节点一路左下，并且一直存储当前遇到的节点，当无法左下的时候，我们弹出当前的栈顶元素，然后往右走一步就可以继续一直左下。这样子，我们就可以满足我们的根左右的顺序，代码如下:

前序遍历

C++ 代码

stack<TreeNode*> s;
vector<int>res;
while(root || !s.empty()) //如果当前栈为空且root不为空，说明还没有开始
                         //如果当前栈的元素还没有全部弹出来说明还有元素没有遍历完
{
    while(root) //让根节点一路左下
    {
        s.push(root);
        res.push_back(root->val);
        root = root->left;
    }
    //当走投无路的时候就要灵活一点啦，往右看看有木有路
    root = s.top();
    s.pop();
    root = root->right;
}
return res;

后序遍历

后序遍历的代码和先序遍历很像，我们只需要先序遍历的时候满足根右左的顺序，最后reverse一下我们的res数组就好啦！

C++ 代码

stack<TreeNode*> s;
vector<int>res;
while(root || !s.empty()) //如果当前栈为空且root不为空，说明还没有开始
                         //如果当前栈的元素还没有全部弹出来说明还有元素没有遍历完
{
    while(root) //让根节点一路右下
    {
        s.push(root);
        res.push_back(root->val);
        root = root->right;
    }
    //当走投无路的时候就要灵活一点啦，往左看看有木有路
    root = s.top();
    s.pop();
    root = root->left;
}
reverse(res.begin(),res.end());
return res;

中序遍历

中序遍历稍微有一丢丢复杂，因为我们不能在左下/右下的过程将当前节点推入最终的数组，我们需要在将最左下的节点弹栈后才能将节点推入最终的数组，这样才能符合中序遍历的左根右的顺序。

C++ 代码

stack<TreeNode*> s;
vector<int>res;
while(root || !s.empty()) //如果当前栈为空且root不为空，说明还没有开始
                         //如果当前栈的元素还没有全部弹出来说明还有元素没有遍历完
{
    while(root) //让根节点一路左下
    {
        s.push(root);
        root = root->left;
    }

    root = s.top();
    s.pop();
    res.push(root->val);
    root = root->right;
}
return res;