Binary Tree Traversal of Iteration (non-recursion)

inorder.cpp

vector<int> inorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> res;

    auto now = root;
    while(!st.empty() || now)
    {
        while(now)
        {
            st.push(now);
            now = now->left;
        }

        if(!st.empty())
        {
            now = st.top(); st.pop();
            res.push_back(now->val);
            now = now->right;
        }
    }
    return res;
}

postorder.cpp

vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> res;

    TreeNode* now = root;
    TreeNode* last = NULL;
    while(!st.empty() || now)
    {
        while(now)
        {
            st.push(now);
            now = now->left;
        }

        if (!st.empty())
        {
            now = st.top();
            if (!now->right || now->right == last)
            {
                res.push_back(now->val);
                st.pop();
                last = now;
                now = NULL;
            }
            else
            {
                now = now->right;
            }
        }
    }
    return res;

}

preorder.cpp

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;

    stack<TreeNode*> st;

    TreeNode* now = root;
    while(!st.empty() || now != NULL)
    {
        while(now)
        {
            st.push(now);
            res.push_back(now->val);
            now = now->left;
        }

        if(!st.empty())
        {
            now = st.top(); st.pop();
            now = now->right;
        }
    }
    return res;
}

• another postorder traversal, using root->right->left form to save, and reverse it will be the correct result.