递归实现二叉树遍历虽然简洁，但迭代方式更能揭示遍历的本质。传统的迭代写法中，前序与后序逻辑相近，而中序却需要借助指针辅助，风格割裂。本文介绍一种标记法，用完全一致的代码框架统一处理三种遍历顺序。

核心思想：访问与处理的分离

迭代遍历的难点在于：访问节点的时机与处理节点（输出值）的时机往往不同步。例如中序遍历需要先深入左子树，回溯后才处理当前节点。

解决方案是引入空指针标记：将待处理的节点入栈后，紧接着压入一个nullptr作为标记。当栈顶为空指针时，说明下一个节点已准备好被处理。

中序遍历实现

中序遍历的顺序为左-根-右。栈中节点的排列需保证：左子树优先访问，当前节点延迟处理。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* curr) {
        vector<int> output;
        stack<TreeNode*> stk;
        if (curr) stk.push(curr);
        
        while (!stk.empty()) {
            TreeNode* top = stk.top();
            if (top) {
                stk.pop();
                // 右子树先入栈（后访问）
                if (top->right) stk.push(top->right);
                // 当前节点标记为待处理
                stk.push(top);
                stk.push(nullptr);
                // 左子树最后入栈（先访问）
                if (top->left) stk.push(top->left);
            } else {
                // 遇到标记，处理节点
                stk.pop();
                TreeNode* ready = stk.top();
                stk.pop();
                output.push_back(ready->val);
            }
        }
        return output;
    }
};

前序遍历：调整入栈顺序

前序遍历为根-左-右。仅需改变子节点的入栈顺序：右子树先入，左子树后入，当前节点标记在最前。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* curr) {
        vector<int> output;
        stack<TreeNode*> stk;
        if (curr) stk.push(curr);
        
        while (!stk.empty()) {
            TreeNode* top = stk.top();
            if (top) {
                stk.pop();
                // 右子树先入栈
                if (top->right) stk.push(top->right);
                // 左子树后入栈
                if (top->left) stk.push(top->left);
                // 当前节点标记（最先处理）
                stk.push(top);
                stk.push(nullptr);
            } else {
                stk.pop();
                TreeNode* ready = stk.top();
                stk.pop();
                output.push_back(ready->val);
            }
        }
        return output;
    }
};

后序遍历：再次调整入栈顺序

后序遍历为左-右-根。当前节点最先入栈标记，随后右子树、左子树依次入栈。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* curr) {
        vector<int> output;
        stack<TreeNode*> stk;
        if (curr) stk.push(curr);
        
        while (!stk.empty()) {
            TreeNode* top = stk.top();
            if (top) {
                stk.pop();
                // 当前节点标记（最后处理）
                stk.push(top);
                stk.push(nullptr);
                // 右子树后访问
                if (top->right) stk.push(top->right);
                // 左子树先访问
                if (top->left) stk.push(top->left);
            } else {
                stk.pop();
                TreeNode* ready = stk.top();
                stk.pop();
                output.push_back(ready->val);
            }
        }
        return output;
    }
};

模式总结

三种遍历的代码结构完全一致，区别仅在于子节点与标记节点的入栈顺序：

遍历类型	入栈顺序（从先到后）
前序	标记节点 → 左子树 → 右子树
中序	右子树 → 标记节点 → 左子树
后序	标记节点 → 右子树 → 左子树

空指针标记法将递归的隐式调用栈显式化，同时统一了迭代遍历的代码风格，便于记忆和维护。