【数据结构与算法】二叉树的非递归遍历算法实现详解（常见面试题）

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;
 
        // 当cur为空且st为空说明已经遍历完了
        while(cur || !st.empty())
        {
            // 1、访问左路节点，左路节点入栈
            while(cur != nullptr)
            {
                st.push(cur);
                v.push_back(cur->val);
                cur = cur->left;
            }

            // 2、依次取左路节点的右子树出来访问
            TreeNode* top = st.top();
            st.pop();
            
            cur = top->right;
        }
        return v;
    }
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;

        while(cur || !st.empty())
        {
            // 1、先将左路节点入栈
            while(cur != nullptr)
            {
                st.push(cur);
                cur = cur->left;
            }

            // 依次取左路节点的右子树进行访问
            // 与前序遍历不同，中序在左路节点全部入栈、访问右子树之前顺便打印或者尾插该节点
            TreeNode* top = st.top();
            st.pop();
            
            v.push_back(top->val);
            
            cur = top->right;
        }
        return v;
    }
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;
        TreeNode* flag = nullptr; //用来标记是否走过该右子树的节点
        while(cur || !st.empty())
        {
            // 1、访问左路节点，左路节点入栈
            while(cur != nullptr)
            {
                st.push(cur);
                cur = cur->left;
            }

            // 2、依次取左路节点的右子树出来访问
            TreeNode* top = st.top();

            //若右子树为空或者右子树已经访问过了（top->right == flag），那么我们就可以访问栈顶元素了
            if(top->right == nullptr || top->right == flag)
            {
                st.pop();
                v.push_back(top->val);
                flag = top; //将top该点赋给flag，说明该点是走过的了
            }
            else
            {
                cur = top->right;
            }
        }
        return v;
    }
};