目錄

為什么可以用迭代法實現二叉樹的前后中序遍歷？

前序遍歷

后序遍歷

中序遍歷

---

為什么可以用迭代法實現二叉樹的前后中序遍歷？

因為遞歸的實現本質是，每次遞歸調用都會把函數的局部變量、參數值和返回地址等壓入調用棧中，然后遞歸返回的時候，從棧頂彈出上一次遞歸的各項參數，這就是遞歸為什么可以返回上一層位置的原因。

所以我們可以用棧實現二叉樹的前中后序遍歷。

前序遍歷

前序遍歷的順序是中左右，我們需要設置一個節點指針用來表示此時遍歷的節點，先將該節點指針初始化為根節點，然后判斷該節點指針是否為空指針，如果為空指針，則返回結果。如果不為空，那么先把根節點放入棧中，然后設置循環直到棧為空時循環結束。循環中將棧頂元素放入結果數組中，并彈出。然后先把該節點的右子節點放入棧中（如果該子節點不為空），把左子節點也放入棧中，然后進行下一次循環，這樣就可保證下次循環先處理的是左子節點。

具體代碼：

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if(root == nullptr) return result;st.push(root);while(!st.empty()) {TreeNode* node = st.top();result.push_back(node->val);st.pop();if(node->right) st.push(node->right);if(node->left) st.push(node->left);}return result;}
};

后序遍歷

后序遍歷的順序是左右中。由于前序遍歷的順序是中左右，我們如果交換左右子節點入棧順序，就可以實現左右子節點的遍歷順序的交換。所以將前序遍歷的左右子節點壓棧語句交換位置，可以實現中右左遍歷順序，然后對最后的結果數組進行翻轉就可以實現左右中遍歷順序，即后序遍歷。

具體代碼：

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> result;if(root == nullptr) return result;st.push(root);while(!st.empty()) {TreeNode* node = st.top();result.push_back(node->val);st.pop();if(node->left) st.push(node->left);if(node->right) st.push(node->right);}reverse(result.begin(), result.end());return result;}
};

中序遍歷

在前序遍歷中主要有兩個操作：

處理：將元素放進result數組中

訪問：遍歷節點

前序遍歷的順序是中左右，先訪問的是中間節點，要處理的元素也是中間節點，即要訪問的元素和要處理的元素順序是一致的。

中序遍歷的順序是左中右，先訪問的是二叉樹頂部的節點，然后一層層向下訪問，直到到達樹左邊的最底部，然后才開始把節點數值放進結果數組中，即處理順序和訪問順序不一致。

具體實現過程是：先設置循環直到棧為空結束循環，此時節點遍歷完畢，返回結果數組。如果棧不為空，或者節點不為空則進入循環體內部，循環體內部需要先判斷節點是否為空。如果不為空，就把該節點放入棧中，然后遍歷下一個左節點（左）。如果節點為空，則將棧頂節點值放入結果數組中（中），然后彈出棧頂元素，同時遍歷該節點的右子節點（右）。

具體代碼：

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;TreeNode* cur = root;while(!st.empty() || cur!=nullptr) {if(cur != nullptr) {st.push(cur);cur = cur->left;}else {TreeNode* node = st.top();st.pop();result.push_back(node->val);cur = node->right;}}return result;}
};