前中后序遍歷（DFS）

首先我們要明確前中后序遍歷的順序：

• 前序：中左右
• 中序：左中右
• 后序：左右中

前中后序遍歷的遞歸代碼和迭代代碼分別有各自的框架，然后根據遍歷順序調整記錄元素的位置即可。

遞歸

class Solution {
private:void postOrder(TreeNode* root, vector<int>& vec) {if (!root) return;postOrder(root->left, vec);	// 1postOrder(root->right, vec);// 2vec.push_back(root->val);		// 3}
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> res;postOrder(root, res);return res;}
};

• 前序遍歷：3->1->2
• 中序遍歷：1->3->2
• 后序遍歷：1->2->3

如前所述，三種遍歷的迭代方式很簡單，并且更改迭代方式只要調整記錄元素的位置即可。

迭代

前序遍歷

我們以前序遍歷給出迭代版本的框架，核心思想就是用棧。

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> S;TreeNode* node = root;while (node || !S.empty()) {while (node) {res.push_back(node->val);			// 注意S.push(node);node = node->left;}node = S.top();		S.pop();node = node->right;	}return res;}
};

中序遍歷

與前序遍歷的差別請看代碼中的 注意，調整了記錄元素的位置。

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {if (!root) return {};vector<int> res;stack<TreeNode*> S;TreeNode* curr = root;while (curr || !S.empty()) {while (curr) {S.push(curr);curr = curr->left;}TreeNode* node = S.top();S.pop();res.push_back(node->val);			// 注意curr = node->right;}return res;}
};

后序遍歷

注意到前序遍歷的順序為：中左右，而我們想要的后序遍歷的順序為：左右中。我們可以先講前序遍歷代碼中訪問左右子樹的順序互換，得到順序為：中右左，再進行 reverse，得到后序：左右中。

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

層序遍歷（BFS）

不需按深度劃分

直接輸出層序遍歷序列，不需按深度劃分，不同于 DFS 使用棧，這里是用隊。

class Solution {
public:vector<int> levelOrder(TreeNode* root) {if (!root) return {};queue<TreeNode*> Q;// vector<vector<int>> res;vector<int> res;Q.push(root);while (!Q.empty()) {TreeNode* curr = Q.front();res.push_back(curr->val);Q.pop();if(curr->left) Q.push(curr->left);if(curr->right) Q.push(curr->right);}return res;}
}

需要按深度劃分

注意在不需要按深度劃分的版本的基礎上做些改變，用 n 記錄當前深度的節點的個數，然后在 for 循環中將這 n 個節點保存到一個數組中，下一層深度再用一個新數組保存，從而達到按深度劃分。

注意在本題的基礎上修改，可解決 LeetCode 中許多層序遍歷的變種問題。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {if (!root) return {};vector<vector<int>> res;queue<TreeNode*> Q;Q.push(root);while (!Q.empty()) {vector<int> vec;int n = Q.size();for (int i=0; i<n; ++i) {TreeNode* curr = Q.front();Q.pop();vec.push_back(curr->val);if (curr->left) Q.push(curr->left);if (curr->right) Q.push(curr->right);}res.push_back(vec);}return res;}
}

Ref：

https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.md