二叉树遍历是一个很常用的基础算法，尤其常用于作为递归转非递归算法的模板。其中，前序遍历常用作无返回值的自顶向下的递归算法的改写，后序遍历常用作带返回值的自底向上的递归算法的改写，例如求树的高度的两种思路。

这里对二叉树的非递归遍历做一个总结，前序、中序、后序使用的都是同一套模板。与递归写法一样，非递归写法也只有结点访问顺序的差别。

太长不看版

// 前序遍历
s.push(make_pair(root->right, false));
s.push(make_pair(root->left, false));
s.push(make_pair(root, true));
// 中序遍历
s.push(make_pair(root->right, false));
s.push(make_pair(root, true));
s.push(make_pair(root->left, false));
// 后序遍历
s.push(make_pair(root, true));
s.push(make_pair(root->right, false));
s.push(make_pair(root->left, false));

递归遍历算法

前序遍历

vector<int> preorder(TreeNode* root, vector<int>& res) {
    if (!root) return res;
    res.push_back(root->val);
    preorder(root->left, res);
    preorder(root->right, res);
    return res;
}

中序遍历

vector<int> inorder(TreeNode* root, vector<int>& res) {
    if (!root) return res;
    inorder(root->left, res);
    res.push_back(root->val);
    inorder(root->right, res);
    return res;
}

后序遍历

vector<int> postorder(TreeNode* root, vector<int>& res) {
    if (!root) return res;
    postorder(root->left, res);
    postorder(root->right, res);
    res.push_back(root->val);
    return res;
}

非递归遍历算法

采用模拟函数栈的方式，递归改非递归的思路：

1. 栈是后入先出，所以右子节点先于左子结点入栈；
2. 标记位记录是否已访问过，用于判断是否到达数据处理阶段/返回阶段；

可以改进的地方：

1. 压栈前判空指针，减少出入栈次数；
2. 前序遍历可以简化，无需标记位，因为新栈顶元素每次入栈后都是立即出栈；

前序遍历

void preorder(TreeNode *root, vector<int>& res)
{
    stack< pair<TreeNode*, bool> > s;
    s.push(make_pair(root, false));
    bool visited;
    while(!s.empty()) {
        root = s.top().first;
        visited = s.top().second;
        s.pop();
        if(root == nullptr) {
            continue;
        }
        if(visited) {
            res.push_back(root->val);
        } else {
            s.push(make_pair(root->right, false));
            s.push(make_pair(root->left, false));
            s.push(make_pair(root, true));
        }
    }
}

中序遍历

void inorder(TreeNode *root, vector<int>& res)
{
    stack< pair<TreeNode*, bool> > s;
    s.push(make_pair(root, false));
    bool visited;
    while(!s.empty()) {
        root = s.top().first;
        visited = s.top().second;
        s.pop();
        if(root == nullptr) {
            continue;
        }
        if(visited) {
            res.push_back(root->val);
        } else {
            s.push(make_pair(root->right, false));
            s.push(make_pair(root, true));
            s.push(make_pair(root->left, false));
        }
    }
}

后序遍历

void postorder(TreeNode *root, vector<int>& res)
{
    stack< pair<TreeNode*, bool> > s;
    s.push(make_pair(root, false));
    bool visited;
    while(!s.empty()) {
        root = s.top().first;
        visited = s.top().second;
        s.pop();
        if(root == nullptr) {
            continue;
        }
        if(visited) {
            res.push_back(root->val);
        } else {
            s.push(make_pair(root, true));
            s.push(make_pair(root->right, false));
            s.push(make_pair(root->left, false));
        }
    }
}