面試必考：二叉樹遞歸與非遞歸遍歷的工程權衡

遞歸 vs 迭代：核心權衡

工程建議

1. 一般業務代碼：首選遞歸。 現代業務樹深度極少超過安全限制（如 DOM 樹、組織架構、分類目錄）。代碼可讀性收益遠大於理論風險。
2. 庫/框架/底層組件/極深度樹：用迭代。 如編譯器 AST 處理、文件系統遍歷、圖算法中 DFS，必須保證 O(1) 或可控棧空間。
3. 面試必會雙寫。 大廠高頻考點：前中後序遞歸 + 迭代（單棧/雙棧/顯式狀態/莫里斯遍歷）。建議熟練掌握統一迭代模板（帶訪問標記的單棧）：

   // 統一模板：前中後序只需調整輸出位置
   vector traversal(TreeNode* root) {
       vector res;
       stack> st; // int: 0=未訪問, 1=左完成, 2=右完成
       if (root) st.emplace(root, 0);
       while (!st.empty()) {
           auto [node, state] = st.top(); st.pop();
           if (!node) continue;
           if (state == 0) { // Pre-order: 處理節點
               // res.push_back(node->val); // 前序位置
               st.emplace(node, 1);
               if (node->left) st.emplace(node->left, 0);
           } else if (state == 1) { // In-order: 左完成
               // res.push_back(node->val); // 中序位置
               st.emplace(node, 2);
               if (node->right) st.emplace(node->right, 0);
           } else { // Post-order: 左右完成
               res.push_back(node->val); // 後序位置
           }
       }
       return res;
   }

4. 莫里斯遍歷 (O(1) 空間) 作為加分項了解，利用葉子節點右指針為空建立線索，遍歷後恢復。面試可口述原理，不必默寫。

總結

「遞歸很耗資源」是相對說法。在 64 位系統、默認 8MB 棧下，遞歸深度達萬級才溢出。除非有明確深度超限證據，否則寫人能看懂的遞歸代碼。 面試時展示「遞歸寫得快、迭代寫得穩、莫里斯知原理」的全棧能力最加分。