0102. Binary Tree Level Order Traversal ======================================= 题目信息 -------- :题号: 0102. 二叉树的层序遍历 :难度: Medium :主题: 二叉树、广度优先搜索、深度优先搜索、队列 :原题: `LeetCode 0102 `_ :重点: 从逐层重复寻找节点,推导到携带深度的一次遍历,再用队列前沿直接维护层边界 题目重述 -------- 给定二叉树根节点 ``root``,按照节点到根的距离从小到大返回所有节点值。返回结果是二维数组:第 ``d`` 个 子数组保存深度为 ``d`` 的全部节点,同一层内必须按照树中从左到右的顺序排列。 结果只包含实际存在的节点,不需要为空孩子保留占位。空树没有任何层,应返回空数组。遍历过程不修改树。 树中节点总数在 ``0..2000`` 范围内,节点值在 ``-1000..1000`` 范围内。 自建示例 -------- * 稀疏结构:``root = [8,4,12,null,6,10,14]``,返回 ``[[8],[4,12],[6,10,14]]``。第三层的 ``6`` 是节点 ``4`` 的右孩子,仍排在节点 ``12`` 的两个孩子之前; * 单侧延伸:``root = [5,null,7,null,9]``,返回 ``[[5],[7],[9]]``。每个深度都只有一个节点; * 单节点:``root = [3]``,返回 ``[[3]]``; * 空树:``root = []``,返回 ``[]``,不能返回包含一个空行的 ``[[]]``。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: void collectAtDepth(TreeNode* node, int currentDepth, int targetDepth, std::vector& level) { if (!node) { return; } if (currentDepth == targetDepth) { level.push_back(node->val); return; } collectAtDepth(node->left, currentDepth + 1, targetDepth, level); collectAtDepth(node->right, currentDepth + 1, targetDepth, level); } std::vector> levelsByRepeatedDepthSearch(TreeNode* root) { std::vector> levels; for (int targetDepth = 0;; ++targetDepth) { std::vector level; collectAtDepth(root, 0, targetDepth, level); if (level.empty()) { break; } levels.push_back(std::move(level)); } return levels; } void collectByDepth(TreeNode* node, int depth, std::vector>& levels) { if (!node) { return; } if (depth == static_cast(levels.size())) { levels.emplace_back(); } levels[depth].push_back(node->val); collectByDepth(node->left, depth + 1, levels); collectByDepth(node->right, depth + 1, levels); } std::vector> levelsByDepthFirstSearch(TreeNode* root) { std::vector> levels; collectByDepth(root, 0, levels); return levels; } std::vector> levelsByBreadthFirstSearch(TreeNode* root) { if (!root) { return {}; } std::vector> levels; std::queue pending; pending.push(root); while (!pending.empty()) { const int levelSize = static_cast(pending.size()); std::vector level; level.reserve(levelSize); for (int count = 0; count < levelSize; ++count) { TreeNode* node = pending.front(); pending.pop(); level.push_back(node->val); if (node->left) { pending.push(node->left); } if (node->right) { pending.push(node->right); } } levels.push_back(std::move(level)); } return levels; } public: std::vector> levelOrder(TreeNode* root) { return levelsByBreadthFirstSearch(root); } }; 题解 ---- 原始分层搜索 ~~~~~~~~~~~~ 题目直接按深度组织输出,因此最直观的正确方案是一次只构造一层。先从根出发寻找深度 ``0`` 的节点,再从 根寻找深度 ``1`` 的节点,随后依次处理 ``2``、``3``,直到某个深度没有节点。 ``collectAtDepth`` 用 ``currentDepth`` 记录当前节点深度,到达 ``targetDepth`` 时保存节点值并停止向下。 递归始终先访问左孩子再访问右孩子,所以同一目标深度的节点会按从左到右的顺序进入 ``level``。每个非空 节点以及它的祖先链都会在对应深度的搜索中被覆盖,因此每一行都完整。 当某次搜索得到空行时可以结束。若深度 ``d + 1`` 存在节点,它的父节点必定位于深度 ``d``;所以深度 ``d`` 为空就意味着所有更深层也为空。这个条件也让空树在第一次搜索后直接返回 ``[]``,而不是加入空行。 重复路径瓶颈 ~~~~~~~~~~~~ 逐层搜索的问题不在正确性,而在于每一层都从根重新出发。寻找深度 ``d`` 的节点时,深度小于 ``d`` 的 全部路径前缀只是通道,却会被再次访问。 在高度为 ``h`` 的树中,每个节点可能作为后续多个目标深度的路径前缀,重复搜索的最坏时间为 ``O(nh)``。 单侧链的第 ``d`` 层需要重新走过前 ``d`` 个节点,总访问量为 ``1 + 2 + ... + n = O(n²)``。输出分层 确实需要知道深度,但没有必要为每个深度重新寻找节点。 深度状态复用 ~~~~~~~~~~~~ 从父节点走到孩子时,孩子深度必然是父节点深度加一。把这个深度随递归状态向下传递,就能在第一次到达节点 时直接确定它属于 ``levels[depth]``,不再保留“目标深度”外层循环,也不再重复经过祖先路径。 ``collectByDepth`` 首次到达深度 ``depth`` 时满足 ``depth == levels.size()``,此时创建新行;之后同层节点 直接追加到已有行。二叉树不可能在尚未到达深度 ``d - 1`` 时先到达深度 ``d``,所以结果不会出现中间缺行, 也不需要预先计算树高。 DFS 会深入左子树后才进入右子树,但这不会破坏层内顺序。任取同一层的两个节点,在它们路径第一次分叉的 祖先处,左侧节点进入左子树,右侧节点进入右子树;先左后右的递归会先访问整个左子树,因此左侧节点必先 追加到对应行。若交换两次递归调用的顺序,结果就会变成每层从右到左。 队列前沿 ~~~~~~~~ DFS 已把时间降到 ``O(n)``,但层边界仍由每个节点携带的 ``depth`` 和结果下标间接表达。题目要求先完成 整层再进入下一层,队列可以让尚未处理的最浅节点形成一个显式前沿。 开始处理某一层时,``pending`` 中已有的节点恰好全部属于当前层。保存此刻的 ``levelSize``,再只弹出这么 多个节点;处理过程中加入队尾的孩子都比父节点深一层,留给下一轮。循环不变量是:每轮外层循环开始时, 队列从头到尾正好是下一行需要输出的节点,且顺序为从左到右。 ``levelSize`` 必须在本层处理前固定。若内层也写成“只要队列非空就继续”,新加入的孩子会立刻被弹出, 所有深度会混入同一个 ``level``。层大小快照不是为了统计节点总数,而是给不断增长的队列划出本轮的终点。 层内顺序 ~~~~~~~~ 当前层父节点已经按从左到右排列。每个父节点出队时先加入左孩子、再加入右孩子,下一层便先按父节点位置、 再按同一父节点的左右方向排列。空孩子不入队,因为返回值不需要占位;跳过空位置不会改变其余非空节点的 相对次序。 以 ``[8,4,12,null,6,10,14]`` 为例,队列边界和输出变化如下: .. list-table:: :header-rows: 1 * - 层 - 开始时 ``pending`` - ``levelSize`` - 本层输出 - 结束时 ``pending`` * - 0 - ``[8]`` - 1 - ``[8]`` - ``[4,12]`` * - 1 - ``[4,12]`` - 2 - ``[4,12]`` - ``[6,10,14]`` * - 2 - ``[6,10,14]`` - 3 - ``[6,10,14]`` - ``[]`` 第二层处理中,弹出 ``4`` 后只加入它的右孩子 ``6``,此时队列暂时是 ``[12,6]``。快照值仍为 ``2``, 所以接着弹出本层剩余的 ``12``,并把 ``10``、``14`` 放到 ``6`` 后面;``6`` 不会提前混入第二行, 下一层顺序也自然成为 ``[6,10,14]``。 代码演进与主解 ~~~~~~~~~~~~~~ ``levelsByRepeatedDepthSearch`` 的目标深度循环让输出结构很直观,但每轮都重新遍历公共路径。 ``levelsByDepthFirstSearch`` 把目标深度改为节点自带的状态,删除外层循环和重复寻层,使每个节点只访问一次; 代价是依赖递归栈,并通过 ``levels[depth]`` 间接聚合各层。 ``levelsByBreadthFirstSearch`` 进一步让队列本身按照深度组织待处理节点。代码不再携带每个节点的深度,改用 一次队列大小快照确定整层边界;先左后右入队同时维护下一层顺序。公开入口采用 BFS,因为它的处理批次与二维 结果的行一一对应,并避免树高较大时的递归调用栈。 另一种写法可以用两个队列分别保存当前层和下一层,但它与单队列加 ``levelSize`` 表达的是同一边界,既不 减少访问次数,也不改善渐进空间,因此不再单列为一种 C++ 方案。 复杂度分析 ~~~~~~~~~~ .. list-table:: :header-rows: 1 * - 方法 - 时间复杂度 - 工作空间 - 主要状态 * - 逐层重复搜索 - ``O(nh)`` - ``O(h)`` - 目标深度与递归路径 * - 携带深度的 DFS - ``O(n)`` - ``O(h)`` - 当前深度与调用栈 * - 单队列 BFS - ``O(n)`` - ``O(w)`` - 当前层和下一层的队列前沿 其中 ``n`` 是节点数,``h`` 是树高,``w`` 是最大层宽。DFS 和 BFS 都只访问每个节点一次;BFS 的每个节点 也只入队、出队一次。复杂度表只统计工作空间,返回结果本身保存全部 ``n`` 个节点值,需要 ``O(n)`` 空间。