否极泰来

佩玉

"朝搴阰之木兰兮，夕揽洲之宿莽。

日月忽其不淹兮，春与秋其代序。"

暴雨来的匆匆，绵绵地，像是欲将这片历史上的霸都泡成烟雨江南。像是歌楼戏子，弦歌不辍，哀转久绝。九月初的太阳昙花一般，一绽即逝，转而陷入长达一个月地阴雨。太匆匆！谢了林红。方才秋分过去，就听闻冬天的踵音，一派“苒苒物华休”的肃秋气象。在这番寒冷的溽气中，我不愿接受这份冷冽的问候，转而躲入那青灯白墙的小楼，自称一统。

珠帘

结束了哈希表的学习，已经在C++的学习进度上欠了很大一笔债。主要忙于补考事物，由于教务处效率低下，排期拉垮，也是拖到现在（2026-10-12）才慢慢有所产出（其实是太懒了，你真是一个大懒虫啊奶油苏打和冕形灯！），然后加上现在赶进度节奏紧凑，到了现在才有所阶段性总结———惭愧··· ···

由于栈与队列的数据结构比较简单，加之现在学习的二叉树与之交集颇多，故而一并付之。

首先是数据结构类型上，最基础的、不含迭代器的结构有 queue, stack ，这两者作为初学者最开始碰到的容器，特性非常简单。queue是FIFO（先进先出）、有两端、保序；stack是LIFO（后进先出）、只有一端、逆序。

对于栈与队列，接口也比较简单，易于记忆，双手可数：empty,top,back,front,push,emplace,pop———没了。接口作用也可以望文生义———但是要注意一点，C++中要使用top/front和pop搭配才相当于python中的pop，top/front/back都是访问，pop才是弹出。

然后，由于栈与队列的操作大多数是对string进行操作，所以大多数题目相对简单（所以刷题的时候顿感 just so so～），当然有兴趣的也可以学我用双栈法完成 Leetcode160———单纯地为了验证自己的想法，误打误撞用到了栈（srds并无必要）。

二叉树的类型比较简单，但是很多时候并无必要分辨，我们着重要讲的是搜索树。其中涉及到四种思想：递归、迭代、深度优先搜索（$Depth-First search$，也作$DFS$）、广度优先搜索（$Breadth-First search$，也作$BFS$）。

以下是我根据不同的搜索顺序和访问顺序的不同组合，完成的层序遍历：

class BFSQueue {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;                       // 层序遍历使用队列
        if (root != nullptr) que.push(root);        // 根节点入队
        vector<vector<int>> result;                 // 结果集

        while (!que.empty()) {                  // 队列不为空，说明还有节点没有遍历完
            int levelSize = static_cast<int>(que.size());   // 当前层的节点数
            vector<int> vec;

// 这里一定要使用固定大小 levelSize，不要直接用 que.size()，因为它在循环中会不断变化

            for (int i = 0; i < levelSize; ++i) {   // 遍历当前层的所有节点
                TreeNode* node = que.front();       // 获取队首节点
                que.pop();                          // 队首节点出队
                vec.push_back(node->val);          // 将当前节点的值加入当前层的结果集

                if (node->left)  que.push(node->left);      // 左子节点入队
                if (node->right) que.push(node->right);     // 右子节点入队
            }
            result.push_back(std::move(vec));       // 本层的结果集收进总结果集
        }
        return result;                              // 返回结果集
    }
};

class BFSRecursive {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;                 // 结果集
        if (root != nullptr) bfsNextLevel({root}, result);     
        // 从"只有根节点"这一层开始
        return result;                              // 返回结果集
    }

private:
    /* 辅助函数：处理"当前层"，并把下一层交给递归 */
    void bfsNextLevel(const vector<TreeNode*>& level, vector<vector<int>>& result) {
        if (level.empty()) return;                  // 本层没有节点，递归结束

        vector<int> vec;                            // 本层的结果集
        vector<TreeNode*> nextLevel;                // 下一层的节点列表

        for (TreeNode* node : level) {              // 依次处理本层的每一个节点
            vec.push_back(node->val);               // 将当前节点的值加入本层的结果集

            if (node->left)  nextLevel.push_back(node->left);       
            // 左子节点作为下一层
            if (node->right) nextLevel.push_back(node->right);      
            // 右子节点作为下一层
        }
        result.push_back(std::move(vec));           // 本层的结果集收进总结果集

        bfsNextLevel(nextLevel, result);            // 递归处理"下一层"
    }
};

class DFSRecursive {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;                 // 结果集
        dfs(root, 0, result);                       // 从根节点、第 0 层开始
        return result;                              // 返回结果集
    }

private:
    /* 辅助函数：先记下当前节点，再一路向左，回溯后向右
       —— 走访顺序是 DFS，节点落在哪一格靠的是深度 */
    void dfs(TreeNode* node, int depth, vector<vector<int>>& result) {
        if (node == nullptr) return;                // 空节点，递归结束

        if (depth == static_cast<int>(result.size()))
            result.push_back({});                   // 第一次到达该深度，新建结果集
        result[depth].push_back(node->val);         // 把当前节点放进对应深度的结果集

        dfs(node->left,  depth + 1, result);        // 先递归左子树
        dfs(node->right, depth + 1, result);        // 再递归右子树
    }
};

class DFSStack {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;                 // 结果集
        if (root == nullptr) return result;         // 空树直接返回

        stack<pair<TreeNode*, int>> st;             // 栈里存"节点 + 深度"
        st.push({root, 0});                         // 根节点入栈，深度为 0

        while (!st.empty()) {                       
        // 栈不为空，说明还有节点没有遍历完
            TreeNode* node = st.top().first;        // 获取栈顶节点
            int depth = st.top().second;            // 获取该节点的深度
            st.pop();                               // 栈顶出栈

        // 当前深度还没有对应的结果集，说明是第一次访问该深度的节点，需要创建一个新的结果集
            if (depth == static_cast<int>(result.size()))
                result.push_back({});               // 创建一个新的结果集

            result[depth].push_back(node->val);     
            // 将当前节点的值加入对应深度的结果集

            if (node->right) st.push({node->right, depth + 1});     // 先压右子节点
            if (node->left)  st.push({node->left,  depth + 1});     
            // 后压左子节点 → 下次先弹出左
        }
        return result;                              // 返回结果集
    }
};

看完这些，头晕是正常的，接下来你可以一个打十个（点题目即跳转 LeetCode）：

#	题目
102	二叉树的层序遍历
107	二叉树的层次遍历 II
199	二叉树的右视图
637	二叉树的层平均值
429	N 叉树的层序遍历
515	在每个树行中找最大值
116	填充每个节点的下一个右侧节点指针
117	填充每个节点的下一个右侧节点指针 II
104	二叉树的最大深度
111	二叉树的最小深度

其中每个题目的答案模板都出自以上四个方法，不同之处只在输出的答案。当我们在面对一个算法题时应该如何思考呢？

首先我们应该考虑：我需不需要跨节点？我需要求树深吗？我的返回类型是什么？我应该选择什么容器？从而我们就可以确定下我们是选择$DFS$还是$BFS$。选择不恰当的容器在进行计算的时候可能会出现容器溢出的报错，从而降低程序的可运行性。

闲云

写到此处，"否"的那一个月忽然不那么难堪了。排期拉垮的补考、欠下的进度、被惰性啃掉的夜晚，都算不得劫难，不过是少年人账本上一笔记不住的亏空。现在所做，不过以往的踵音。

仍记得高中背的一篇小散文，王佐良先生翻译的$Youth$：“青春气贯长虹，勇锐盖过怯弱，进取压倒苟安。”这并非是社会达尔文主义抑或优绩主义，只是为了逃避那个用试卷就能被定义的怪圈，那个被形式主义浸泡的校园，那个无时无刻不被人定义的过去。

反动的、盲目的、片面的、冰冷的、否定的，进步的对立面矗立于眼前，我无法忽视这头客厅里的大象，无法任由其压迫我的呼吸。大雪深埋中，我无法得知我是否能够如同彼时的姚刑部一样，探得那“苍山负雪，明烛天南”。

十月的夜，雨歇了，青灯白墙的小楼仍是那小楼。抬颌时，墙上映着两个影子，一个伏案，一个长明。所谓否极泰来，从来不是天光忽然回转，而是一个人走到最暗处的路上，仍未搁笔。