企业官网建设流程全解析

LeetCode 222：完全二叉树节点计数 —— LeetCode-Go 仓库 BFS 层序统计解法全解析

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

LeetCode 第 222 题要求在 $O(n)$ 级别遍历并统计一棵**完全二叉树（Complete Binary Tree）**的节点总数。本文以 LeetCode-Go 仓库中leetcode/0222.Count-Complete-Tree-Nodes目录下的题解为主体，从完全二叉树的严格定义出发，逐行拆解仓库采用的 BFS 层序遍历实现，并结合测试用例与 structures 工具库说明如何构建测试树、验证结果。读完本文，你将掌握"按层计数"这一最直观的完全二叉树统计方案，理解其在最坏情况下的时间复杂度与空间复杂度，并了解完全二叉树特性带来的更优解法思路。

题目描述与完全二叉树的定义

题目原文要求：给定一棵完全二叉树（complete binary tree），统计其节点个数。

根据题目引用的维基百科定义：

在一棵完全二叉树中，除最后一层外，每一层都是完全填满的；且最后一层的所有节点都尽可能靠左排列。在最后一层（高度为 h）上，节点数介于 1 到 2^h 之间（含端点）。

题目给出的示例如下：

Input: 1 / \ 2 3 / \ / 4 5 6 Output: 6

这棵树共 6 个节点：根节点 1，第二层节点 2、3 全部填满，最后一层（第三层）节点 4、5、6 从左侧开始连续排列——恰好符合"最后一层节点尽可能靠左"的完全二叉树特征。

题目大意

输出一棵完全二叉树的节点个数。注意本题与普通二叉树计数问题的区别在于输入带有"完全二叉树"这一结构性约束，因此除了朴素的全体遍历外，还可以利用其"各层除最后一层外全部填满、最后一层左对齐"的性质做剪枝或二分优化；当然，最直接的思路仍是按层序遍历一次整棵树，把每一层的节点数累加起来，这正是仓库题解采用的方法。

解题思路：BFS 层序遍历逐层累加

原文档给出的核心思路是：

这道题其实按照层序遍历一次树，然后把每一层的结点个数相加即可。

对应到仓库实现 222. Count Complete Tree Nodes.go，整体策略可以概括为三步：

1. 空树特判：根节点为nil时直接返回 0；
2. 按层遍历：借助队列做广度优先遍历，同时维护"当前层剩余待处理节点数"与"下一层节点数"两个计数器；
3. 逐层累加：每当一层处理完毕，就把下一层的节点数累加到结果中，直至队列为空。

这种做法的正确性不依赖"完全二叉树"这一特殊性质——它对任意二叉树都成立，因此实现简单、不易出错，代价是要访问全部节点。

源码逐段解析

仓库中的解法完整代码如下（为便于理解，此处按逻辑分段说明，实际文件即 222. Count Complete Tree Nodes.go）：

func countNodes(root *TreeNode) int { if root == nil { return 0 } queue := []*TreeNode{} queue = append(queue, root) curNum, nextLevelNum, res := 1, 0, 1 for len(queue) != 0 { if curNum > 0 { node := queue[0] if node.Left != nil { queue = append(queue, node.Left) nextLevelNum++ } if node.Right != nil { queue = append(queue, node.Right) nextLevelNum++ } curNum-- queue = queue[1:] } if curNum == 0 { res += nextLevelNum curNum = nextLevelNum nextLevelNum = 0 } } return res }

类型别名与节点定义

函数签名中的TreeNode在文件顶部通过类型别名声明：

// TreeNode define type TreeNode = structures.TreeNode

它直接复用了仓库 structures/TreeNode.go 中定义的树节点结构：

type TreeNode struct { Val int Left *TreeNode Right *TreeNode }

整个 LeetCode-Go 仓库的树类题目都统一复用这一结构定义，避免每个题目重复声明。

关键变量语义

• queue：层序遍历用的队列，初始只含根节点；
• curNum：当前层还有多少个节点等待出队处理，初始为 1（根节点所在层）；
• nextLevelNum：下一层已入队的节点数，即下一层的宽度；
• res：累计的节点总数，初始为 1（已计入根节点）。

循环体工作流程

外层for len(queue) != 0保证队列清空即遍历结束。内层通过curNum是否大于 0 控制当前层的处理节奏：

1. 每次从队首取出一个节点（queue[0]）；
2. 若其左孩子存在，入队并让nextLevelNum++；右孩子同理；
3. 处理完当前节点后curNum--，并弹出队首元素（queue = queue[1:]）；
4. 当curNum减到 0，说明当前层已全部处理完毕，此时把nextLevelNum（下一层节点数）累加到res，并让curNum = nextLevelNum、nextLevelNum = 0，进入下一轮循环处理新的一层。

以题目示例手工推演

对示例树[1, 2, 3, 4, 5, 6]的推演过程如下：

最终res = 6，与题目预期输出一致。

测试用例与验证

仓库为本题配套了完整的测试文件 222. Count Complete Tree Nodes_test.go，采用"参数-期望值"结构组织用例：

qs := []question222{ {para222{[]int{}}, ans222{0}}, // 空树 {para222{[]int{1}}, ans222{1}}, // 单节点 {para222{[]int{1, 2, 3}}, ans222{3}}, // 两层满树 {para222{[]int{1, 2, 3, 4, 5, 6}}, ans222{6}}, // 题目示例 }

测试中通过structures.Ints2TreeNode(p.one)把整数切片还原成二叉树。该工具函数同样定义在 structures/TreeNode.go 中，其规则是：

• 空切片返回nil（空树）；
• 以切片首元素为根，借助队列按**层序（BFS 顺序）**逐个挂接左右孩子；
• 切片中的NULL标记（var NULL = -1 << 63）表示该位置没有节点。

例如切片[1, 2, 3, 4, 5, 6]会被还原为示例中那棵 6 节点的完全二叉树。这也是本仓库所有二叉树题目共用的建树约定，读者自行编写测试时可照此方式快速构造树形输入。

如何运行测试

在仓库根目录执行：

go test ./leetcode/0222.Count-Complete-Tree-Nodes/... -v

即可看到Test_Problem222的逐条输入输出。仓库根目录的 gotest.sh 还提供了全量测试入口：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

该脚本会对./leetcode/...下所有题目包统一执行带覆盖率收集的测试，生成根目录的coverage.txt，这正是仓库"100% test coverage"目标的来源。

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为节点总数。BFS 需要访问每个节点恰好一次，队列操作（入队、出队）均为常数时间。
• 空间复杂度：$O(w)$，其中 $w$ 为队列中同时存在的最大节点数。对于完全二叉树，最宽的一层出现在最后一层附近，宽度上界为 $\lceil n/2 \rceil$，因此空间复杂度为 $O(n)$ 量级；若严格以完全二叉树高度 $h$ 表达，则为 $O(2^h)$。

延伸思考：利用完全二叉树性质的更优解法

仓库题解选择了通用且稳妥的 BFS 全遍历方案。但从算法进阶角度，完全二叉树的特殊结构还允许我们做到 $O(\log^2 n)$：

• 先沿着最左路径求出树高 $h$；
• 若右子树最左路径也能达到高度 $h$，说明左子树是满二叉树，其节点数为 $2^{h-1}-1$，只需递归统计右子树；
• 否则右子树高度不足，说明最后一层节点未延伸到右子树，此时右子树是高度为 $h-1$ 的满二叉树，递归统计左子树即可。

每一层只做一次高度探测（$O(h)$），共递归 $O(h)$ 层，因此总复杂度为 $O(h^2)=O(\log^2 n)$。这类解法属于本题的经典进阶方案，读者可以在掌握仓库的 BFS 实现后自行推导验证。

小结

LeetCode 222 题"统计完全二叉树节点数"在 LeetCode-Go 仓库中的标准解法是 BFS 层序遍历加逐层累加：countNodes 通过curNum与nextLevelNum两个计数器精确切分每一层，逻辑清晰、对任意二叉树均适用；配套测试覆盖空树、单节点、两层满树与题目示例四类场景，并结合 Ints2TreeNode 完成了从数组到二叉树的快速建树。无论面试中是被要求"先给出最直观解法"，还是进一步追问"能否利用完全二叉树性质优化"，掌握了 BFS 基线实现后都能从容应对。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go