題目鏈接

• LeetCode102.二叉樹的層序遍歷：102. 二叉樹的層序遍歷 - 力扣（LeetCode）
• LeetCode103.二叉樹的鋸齒形層序遍歷：103. 二叉樹的鋸齒形層序遍歷 - 力扣（LeetCode）

實現思路

1. 定義一個隊列，每一輪循環，隊列都會放入新的一層的節點；
2. 在下一次循環中，取出上一層放入的所有新節點（放入數組中），并依次從隊列中踢出這些節點，獲取到這些節點的左右孩子，再放入隊列中。如此，就達到了1中所說的每一輪循環，最終隊列放入的都是新遍歷的層次的所有節點（從左到右）。
3. 鋸齒形：用一個遍歷來標記奇/偶數層，奇數層時數組順序存放在結果中，反之，逆序。

代碼實現

• LeetCode102.二叉樹的層序遍歷

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ans;if (root == nullptr) return ans;queue<TreeNode*> q;q.push(root);while (int s = q.size()) {vector<int> res;for (int i = 0; i < s; i++) {TreeNode* top = q.front();res.push_back(top->val);q.pop();if (top->left) q.push(top->left);if (top->right) q.push(top->right);}ans.push_back(res);}return ans;}
};

• LeetCode103.二叉樹的鋸齒形層序遍歷

class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> res;if (root == nullptr) return res;queue<TreeNode*> q;q.push(root);bool flag = 0;while (int s = q.size()) {vector<int> ans;TreeNode* cur;for (int i = 0; i < s; i++) {cur = q.front();ans.push_back(cur->val);if (cur->left) q.push(cur->left);if (cur->right) q.push(cur->right);q.pop();}if (flag) reverse(ans.begin(), ans.end());res.push_back(ans);flag = !flag;}return res;}
};