[数据结构与算法]二叉树的迭代遍历

二叉树的迭代遍历其实蛮简单的，核心就是栈。中序和后序遍历，需要考虑根节点是否看过，需要在栈中存pair，判断是否遍历过。对于前序遍历则不需要。

三种遍历方式代码都蛮像的。

前序：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> ans;
        if(!root)return ans;
        s.push(root);
        while(!s.empty())
        {
            auto p = s.top(); s.pop();
            if(!p)continue;
            ans.push_back(p->val);
            s.push(p->right);
            s.push(p->left);
        }
        return ans;
    }
};

中序：

class Solution {
typedef pair<int, TreeNode*> P;
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<P> s;
        s.push(P(0, root));
        vector<int> ans;

        while(!s.empty())
        {
            auto top = s.top(); s.pop();
            auto p = top.second;
            if(!p)continue;
            if(top.first == 0)
            {
                s.push(P(0, p->right));
                s.push(P(1, p));
                s.push(P(0, p->left));
            }
            else ans.push_back(p->val);
        }
        return ans;
    }
};

后序：

class Solution {
typedef pair<int, TreeNode*> P;
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<P> s;
        s.push(P(0, root));
        vector<int> ans;

        while(!s.empty())
        {
            auto top = s.top(); s.pop();
            auto p = top.second;
            if(!p)continue;
            
            if(top.first == 0)
            {
                s.push(P(1, p));
                s.push(P(0, p->right));
                s.push(P(0, p->left));
            }
            else ans.push_back(p->val);
        }

        return ans;
    }
};