来自左神讲解，观看b站更精彩。
1.二叉树层序遍历
解法一
#include <iostream> #include <queue> #include <unordered_map> using namespace std; class LevelOrderTraversal { private: struct TreeNode { int val; TreeNode *left, *right; TreeNode() : val(0), left(NULL), right(NULL) {} TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; unordered_map<TreeNode*, int> levels; public: vector<vector<int>> levelOrder(TreeNode* root) { if (!root) return {}; vector<vector<int>> vec; queue<TreeNode*> q; q.push(root); levels[root] = 0; while (!q.empty()) { TreeNode* node = q.front(); q.pop(); int level = levels[node]; if (node->left != nullptr) { q.push(node->left); levels[node->left] = level + 1; } if (node->right != nullptr) { q.push(node->right); levels[node->right] = level + 1; } if (vec.size() == level) { vec.push_back(vector<int>()); } vec[level].push_back(node->val); } return vec; } };解法二（更推荐）
#include <iostream> #include <queue> #include <unordered_map> using namespace std; class LevelOrderTraversal { private: struct TreeNode { int val; TreeNode *left, *right; TreeNode() : val(0), left(NULL), right(NULL) {} TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; unordered_map<TreeNode*, int> levels; public: static const int MAXN = 2001; TreeNode* queArray[MAXN]; int l, r = 0; vector<vector<int>> levelOrder(TreeNode* root) { if (!root) return {}; vector<vector<int>> ans; l = r = 0; // 初始化数组 queArray[r++] = root; // 将根节点入队 while (l < r) { int size = r - l; vector<int> list; for (int i = 0; i < size; ++i) { TreeNode* node = queArray[l++]; list.push_back(node->val); if (node->left != nullptr) { queArray[r++] = node->left; } if (node->right != nullptr) { queArray[r++] = node->right; } } ans.push_back(list); } return ans; } };
