題目

94. 二叉樹的中序遍歷 - 力扣（LeetCode）

什么是中序遍歷

二叉樹的中序遍歷是按照"左-根-右"的順序訪問二叉樹中的所有節點。

具體過程：

• 先遍歷左子樹（遞歸）
• 然后訪問根節點
• 最后遍歷右子樹（遞歸）

例如，對于下面的二叉樹：

    1/ \2   3/ \   \
4   5   6

中序遍歷的結果是：[4, 2,?5, 1, 3,?6]

遍歷步驟：

• 從根節點開始，先訪問左子樹
• 訪問節點4（左葉子）
• 訪問節點2（4的父節點）
• 訪問節點5（2的右子節點）
• 訪問節點1（根節點）
• 訪問節點3（右子節點）
• 訪問節點6（3的右子節點）

遞歸寫法

讀者可能會出現的錯誤寫法

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

在dfs函數中，result參數是按值傳遞的，而不是按引用傳遞的，這會導致對result的修改不會保存。

每次調用dfs函數時：

1. 會創建result的一個新副本
2. 當執行result.push_back(root->val)時，只是向這個副本中添加元素
3. 遞歸調用子節點的dfs時，又會創建新的副本
4. 當函數返回時，這個副本被銷毀，其中存儲的所有節點值都消失了

正確寫法

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

非遞歸寫法

思路

• 沿著左子樹一直深入，將所有節點壓入棧中

• 當無法繼續向左時，彈出棧頂節點，訪問它

• 然后處理該節點的右子樹

具體實現步驟：

• 創建一個空棧和一個指向當前節點的指針curr（初始為根節點）

• 當curr不為空或棧不為空時循環：

• 如果curr不為空，將curr壓入棧，然后curr移動到其左子節點

• 如果curr為空，彈出棧頂節點，將其值加入結果數組，然后curr移動到其右子節點

讀者可能的錯誤寫法

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*>st;TreeNode* node = root;while(node || !st.empty()){while(node){st.push(node);node=node->left;}//將棧頂的元素放入數組中result.push_back(node->val);st.pop();node = node->right;}return result;}
};

在嘗試訪問node->val之前，node已經是nullptr。在內層while循環結束后，node已經是nullptr，因為循環的終止條件就是node為空。因此，在這之后直接訪問node->val和node->right會導致空指針解引用錯誤。

正確的方法

vector<int> inorderTraversal(TreeNode* root) 
{vector<int> result;stack<TreeNode*> st;TreeNode* node = root;while(node || !st.empty()){while(node){st.push(node);node = node->left;}node = st.top();  // 先獲取棧頂節點st.pop();result.push_back(node->val);node = node->right;}return result;
}