二叉樹非遞歸遍歷：從遞歸到棧的思維轉換

為什麼要非遞歸？

遞歸雖然代碼簡潔，但存在棧溢位風險（深度過大時），且在嵌入式或高性能場景下，手動管理棧能更精確控制記憶體與效能。

核心洞察：遞歸本質就是棧

遞歸調用時，系統自動保存「返回地址」與「區域變數」到呼叫棧。非遞歸遍歷，就是我們手動模擬這個過程：用一個顯式的 stack<Node*> 保存「尚未處理的節點」。

前序遍歷非遞歸模板

void preorderIterative(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* cur = st.top(); st.pop();
        visit(cur);                 // 處理當前節點
        if (cur->right) st.push(cur->right); // 先右後左，保證左子樹先被處理
        if (cur->left)  st.push(cur->left);
    }
}

中序遍歷非遞歸模板

void inorderIterative(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) {               // 一路向左，沿途節點入棧
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top(); st.pop();   // 取出最左節點
        visit(cur);                 // 處理
        cur = cur->right;           // 轉向右子樹
    }
}

後序遍歷非遞歸（雙棧法）

void postorderIterative(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> s1, s2;
    s1.push(root);
    while (!s1.empty()) {
        TreeNode* cur = s1.top(); s1.pop();
        s2.push(cur);               // 先存入第二棧
        if (cur->left)  s1.push(cur->left);
        if (cur->right) s1.push(cur->right);
    }
    while (!s2.empty()) {           // 依序彈出即為後序
        visit(s2.top()); s2.pop();
    }
}

如何自己推導出來？

1. 先寫出遞歸版本，觀察「什麼時候訪問節點」、「什麼時候進左/右子樹」。
2. 用棧保存「待處理節點」與「狀態」（如是否已處理左子樹）。
3. 對應每種遍歷順序，調整入棧/出棧順序與訪問時機。
4. 多畫幾棵樹在紙上跑一遍，腦中建立「棧模擬呼叫棧」的直覺。

歷史小注

二叉樹概念由哈夫曼（Huffman）於 1952 年提出，但非遞歸遍歷演算法是後來軟體工程師為解決實際工程問題（棧溢位、效能）而發展出的工程實踐，並非單一發明者。重點在於掌握「用棧模擬遞歸」這通用技巧，可應用於圖的 DFS、表達式求值等眾多場景。