二叉樹的層序遍歷和前中后序遍歷代碼 迭代/遞歸

只記錄代碼。思路參考代碼隨想錄：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。

前中后序遍歷（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

迭代

前序遍歷

版本1:

版本1和層序遍歷很像，區別在于這里是用棧，層序是用隊。注意這也可以作為后序遍歷的迭代版本的基石。

class Solution { private:vector<int> res;void preOrder(TreeNode* root) {if (!root) return;res.push_back(root->val);if (root->left) return preOrder(root->left);if (root->right) return preOrder(root->right);} public:vector<int> preorderTraversal(TreeNode* root) {preOrder(root);return res;} };

版本2:

與中序遍歷的差別請看代碼中的 注意，注意前/中序遍歷 push_back 元素位置的不同。

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;} };

中序遍歷

與前序遍歷版本2的差別請看代碼中的 注意，注意前/中序遍歷 push_back 元素位置的不同。

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）

不需按深度劃分

直接輸出層序遍歷序列，不需按深度劃分，與前序遍歷序列版本一有點像，區別在于這里是用隊，前序使用棧。

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;} }

總結

以上是生活随笔為你收集整理的二叉树的层序遍历和前中后序遍历代码 迭代/递归的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。