LeetCode Binary Tree Preorder Traversal：栈模拟迭代实现

题目要求

二叉树前序遍历（根-左-右），必须用迭代非递归实现。

迭代 vs 递归

• 递归：函数自我调用，利用系统栈
• 迭代：显式栈数据结构，手动管理遍历状态

栈模拟算法

1. 根节点入栈
2. 栈不空时：弹出节点，记录值，右子节点入栈，左子节点入栈（先右后左，保证左先出）

C++ 实现

class Solution {
public:
    vector preorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector res;
        stack st;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top(); st.pop();
            res.push_back(node->val);
            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
        }
        return res;
    }
};

复杂度

• 时间：O(n) 每节点进出栈一次
• 空间：O(h) 栈深度 ≤ 树高，最坏 O(n)

扩展：统一框架（颜色标记法）

vector preorderTraversal(TreeNode* root) {
    vector res;
    stack> st; // 0=未访问, 1=已访问
    if (root) st.emplace(root, 0);
    while (!st.empty()) {
        auto [node, state] = st.top(); st.pop();
        if (!node) continue;
        if (state) res.push_back(node->val);
        else {
            if (node->right) st.emplace(node->right, 0);
            if (node->left) st.emplace(node->left, 0);
            st.emplace(node, 1);
        }
    }
    return res;
}

该框架易扩展为中序/后序（调整入栈顺序与标记时机）。