二叉樹非遞歸遍歷總結：前序、中序、後序

通用思路

用顯式棧模擬遞歸調用棧。前序、中序、後序只需調整入棧順序與輸出時機。

前序遍歷

vector preorder(TreeNode* root) {
    vector res;
    stack st;
    if (root) st.push(root);
    while (!st.empty()) {
        TreeNode* n = st.top(); st.pop();
        res.push_back(n->val);
        if (n->right) st.push(n->right);
        if (n->left) st.push(n->left);
    }
    return res;
}

中序遍歷

vector inorder(TreeNode* root) {
    vector res;
    stack st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur = cur->left; }
        cur = st.top(); st.pop();
        res.push_back(cur->val);
        cur = cur->right;
    }
    return res;
}

後序遍歷

vector postorder(TreeNode* root) {
    vector res;
    stack st;
    if (root) st.push(root);
    while (!st.empty()) {
        TreeNode* n = st.top(); st.pop();
        res.push_back(n->val);
        if (n->left) st.push(n->left);
        if (n->right) st.push(n->right);
    }
    reverse(res.begin(), res.end()); // 反轉得後序
    return res;
}

關鍵點

• 前序：根→左→右，棧先壓右後壓左。
• 中序：左→根→右，沿左鏈入棧，彈出訪問再轉右。
• 後序：左→右→根，利用「根→右→左」反轉技巧最簡潔。