• 🙋?♂? 作者：海碼007
• 📜 專欄：算法專欄
• 💥 標題：【Hot 100】94. 二叉樹的中序遍歷
• ?? 寄語：書到用時方恨少，事非經過不知難！

引言

今天開始二叉樹的篇章，繼續加油。

二叉樹的中序遍歷

• 🎈 題目鏈接：https://leetcode.cn/problems/binary-tree-inorder-traversal/description/?envType=study-plan-v2&envId=top-100-liked
• 🎈 做題狀態：

我的解題

二叉樹的遍歷有四種，分別是前序、中序、后序以及層次遍歷。前中后序遍歷可以通過遞歸寫出清晰的代碼，當然也可以通過棧來寫出非遞歸的代碼。然后是層次遍歷通過借助隊列來實現一層一層的遍歷順序。

下面來解析一下我的代碼，本題給出的核心函數是 inorderTraversal 然后函數有一個返回值，這個返回值記錄的是二叉樹的值。如果我直接將 inorderTraversal 作為一個遞歸函數來寫的話，就需要處理這個返回值，要考慮如何將這個返回值合并。所以為了讓記錄變得更加方便我新建了一個遞歸函數 midTraversal ，這個函數沒有返回值，但是使用了引用傳遞來讓這個結果合并起來。

class Solution {
public:void midTraversal(TreeNode* node, vector<int>& data){if (!node) return;midTraversal(node->left, data);data.push_back(node->val);midTraversal(node->right, data);}vector<int> inorderTraversal(TreeNode* root) {vector<int> res;midTraversal(root, res);return res;}
};

代碼優化

1. 遞歸函數的返回值問題：

   • 如果直接讓 inorderTraversal 遞歸調用自身，每次遞歸都需要合并子樹的遍歷結果（即處理返回值），這會增加代碼復雜度。
   • 例如：

     vector<int> inorderTraversal(TreeNode* root) {if (!root) return {};auto left = inorderTraversal(root->left);  // 需要合并左子樹的結果auto right = inorderTraversal(root->right); // 需要合并右子樹的結果left.push_back(root->val);                // 插入當前節點left.insert(left.end(), right.begin(), right.end()); // 合并右子樹return left; // 返回合并后的結果
     }
     

   • 這種寫法需要頻繁合并向量，效率較低（時間復雜度為 O(n^2)），且代碼冗余。

2. 引用傳遞的優化：

   • 通過引入輔助函數 midTraversal，將結果向量 data 通過引用傳遞，避免返回值合并的問題。
   • 遞歸過程中直接修改同一個 data 向量，無需合并，效率更高（時間復雜度 O(n)）。

---

更清晰的表述建議：

“中序遍歷的遞歸實現需要按左子樹->根節點->右子樹的順序訪問節點。如果直接在 inorderTraversal 中遞歸，每次遞歸調用會返回一個獨立的向量，需要將這些向量合并（如拼接左子樹、當前節點、右子樹的結果），效率較低。
因此，我引入輔助函數 midTraversal，通過引用傳遞一個共享的結果向量 data。遞歸過程中，所有節點值直接追加到 data 中，無需合并操作，既簡化了代碼，又保證了線性時間復雜度。”