我們以中序遍歷為例，在二叉樹：聽說遞歸能做的，棧也能做！?(opens new window)中提到說使用棧的話，無法同時解決訪問節點（遍歷節點）和處理節點（將元素放進結果集）不一致的情況。

那我們就將訪問的節點放入棧中，把要處理的節點也放入棧中但是要做標記。

方法一：就是要處理的節點放入棧之后，緊接著放入一個空指針作為標記。?這種方法可以叫做空指針標記法。

1. 前序遍歷（根 -> 左 -> 右）：

   • 壓棧順序：右子節點 -> 左子節點 -> 當前節點 ->?NULL。

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

1. 中序遍歷（左 -> 根 -> 右）：

   • 壓棧順序：右子節點 -> 當前節點 ->?NULL?-> 左子節點。

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

1. 后序遍歷（左 -> 右 -> 根）：

   • 壓棧順序：當前節點 ->?NULL?-> 右子節點 -> 左子節點。

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

方法二：加一個?boolean?值跟隨每個節點，false?(默認值) 表示需要為該節點和它的左右兒子安排在棧中的位次，true?表示該節點的位次之前已經安排過了，可以收割節點了。?這種方法可以叫做boolean 標記法，樣例代碼見下文C++ 和 Python 的 boolean 標記法。 這種方法更容易理解，在面試中更容易寫出來。

Boolean 標記法的核心思想

1. 標記的作用：

   • false：表示該節點需要被“安排”（即需要處理其子節點）。

   • true：表示該節點已經被“安排”過，可以直接收割（加入結果集）。

2. 棧的使用：

   • 棧中存儲的是?pair<TreeNode*, bool>，其中?bool?表示節點的狀態。

3. 遍歷順序：

   • 根據前序、中序、后序遍歷的要求，調整節點的壓棧順序。

visited?是一個布爾值（bool），用于標記當前節點是否已經被“處理”過。它的作用是區分節點的兩種狀態：

1. visited = false：

   • 表示該節點?需要被安排，即需要處理其子節點。

   • 此時，節點會被重新壓入棧中，并按照遍歷順序（前序、中序、后序）調整其子節點的壓棧順序。

2. visited = true：

   • 表示該節點?已經被安排過，可以直接“收割”（將其值加入結果集）。

   • 此時，節點不再需要處理其子節點。

vector<int> traversal(TreeNode* root) {vector<int> result;if (!root) return result;stack<pair<TreeNode*, bool>> st;st.push({root, false}); // 初始狀態為 false，表示需要安排子節點while (!st.empty()) {auto [node, visited] = st.top();st.pop();if (visited) {// 如果節點已經被訪問過，直接收割result.push_back(node->val);} else {// 根據遍歷順序調整壓棧順序// 前序：根 -> 左 -> 右// 中序：左 -> 根 -> 右// 后序：左 -> 右 -> 根if (node->right) st.push({node->right, false}); // 右子節點st.push({node, true}); // 當前節點標記為已訪問if (node->left) st.push({node->left, false});   // 左子節點}}return result;
}