HHot 100C++ 图解

102. 二叉树的层序遍历

中等 二叉树 3 帧动画 在力扣上做

一句话套路BFS 按层出队,用 size 定层宽

题目描述

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

 

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]

示例 2:

输入:root = [1]
输出:[[1]]

示例 3:

输入:root = []
输出:[]

 

提示:

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

思路

时间O(n)
空间O(最宽一层) = O(n)

思路

BFS + 「进入循环前先记下 q.size()」,这个 size 就是当前层的结点数,于是天然把层与层分开。Q199 右视图 / Q103 锯齿 / Q107 自底向上都改这一行。

图解

9 3 15 20 7
二叉树(来自本仓库测试数据,nullopt 表示空位)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/08_binary_tree.cpp24 行
namespace lc0102 {
class Solution {
 public:
  vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ans;
    if (!root) return ans;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
      int sz = (int)q.size();  // 本层结点数,关键一步
      ans.emplace_back();
      ans.back().reserve(sz);
      for (int i = 0; i < sz; ++i) {
        TreeNode* cur = q.front();
        q.pop();
        ans.back().push_back(cur->val);
        if (cur->left) q.push(cur->left);
        if (cur->right) q.push(cur->right);
      }
    }
    return ans;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q102_level_order8 行
lc0102::Solution s;
TreeNode* a = buildTree({3, 9, 20, nullopt, nullopt, 15, 7});
CHECK_EQ(s.levelOrder(a), vector<vector<int>>({{3}, {9, 20}, {15, 7}}));
freeTree(a);
CHECK_EQ(s.levelOrder(nullptr), vector<vector<int>>{});
TreeNode* b = buildTree({1});
CHECK_EQ(s.levelOrder(b), vector<vector<int>>({{1}}));
freeTree(b);

↑↓ 选择↵ 打开/ 随时唤起