BFS

LeetCode 958 https://leetcode.cn/problems/check-completeness-of-a-binary-tree/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 层序遍历二叉树。如果遍历到了一个非空节点之前遍历过空节点，就不是完全二叉树。 时间复杂度：O(N)，其中 N 是树节点个数。 空间复杂度：O(N)。 ...

LeetCode 297 https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题可以使用前序遍历或者层序遍历，这里使用层序遍历。 在序列化时需要注意空节点也需要保存。在反序列化时，为了分割字符串，使用了 stringstream。 getline(ss, token, ',') 序列化和反序列化的时空复杂度相同。 时间复杂度：O(n)。 空间复杂度：O(n)。 ...

LeetCode 662 https://leetcode.cn/problems/maximum-width-of-binary-tree/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 这道题类似二叉树层序遍历，但是除了要保留节点本身，还需要保留节点在本层的编号。对节点 i，左儿子为 2 * i，右儿子为 2 * i + 1。 另外，由于最大 3000 个节点，如果是一条只有右儿子的链，那么编号会达到 \(2^3000\)，任何数据类型都会溢出，所以我们需要使用 unsigned long long 类型，当溢出后会重新回到 0，而不会报错。 时间复杂度：O(n)，其中 n 是二叉树的节点个数。需要遍历所有节点。 空间复杂度：O(n)。广度优先搜索的空间复杂度最多为 O(n)。 ...

LeetCode 103 https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 这道题类似 LeetCode 102，只是需要判断当前层的奇偶性，如果是偶数，需要把当前层的结果翻转后再加入答案。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。满二叉树（每一层都填满）最后一层有大约 n/2 个节点，因此数组中最多有 O(n) 个元素，所以空间复杂度是 O(n) 的。 ...

LeetCode 102 https://leetcode.cn/problems/binary-tree-level-order-traversal/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 这道题是 BFS 的经典题目。本题使用两个数组 cur 和 nxt 来实现 BFS。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。满二叉树（每一层都填满）最后一层有大约 n/2 个节点，因此数组中最多有 O(n) 个元素，所以空间复杂度是 O(n) 的。 ...