尧图网站建设 
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整体策略可以概括为三步空树特判根节点为nil时直接返回 0按层遍历借助队列做广度优先遍历同时维护当前层剩余待处理节点数与下一层节点数两个计数器逐层累加每当一层处理完毕就把下一层的节点数累加到结果中直至队列为空。这种做法的正确性不依赖完全二叉树这一特殊性质——它对任意二叉树都成立因此实现简单、不易出错代价是要访问全部节点。源码逐段解析仓库中的解法完整代码如下为便于理解此处按逻辑分段说明实际文件即 222. Count Complete Tree Nodes.gofunc 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 控制当前层的处理节奏每次从队首取出一个节点queue[0]若其左孩子存在入队并让nextLevelNum右孩子同理处理完当前节点后curNum--并弹出队首元素queue queue[1:]当curNum减到 0说明当前层已全部处理完毕此时把nextLevelNum下一层节点数累加到res并让curNum nextLevelNum、nextLevelNum 0进入下一轮循环处理新的一层。以题目示例手工推演对示例树[1, 2, 3, 4, 5, 6]的推演过程如下阶段curNumnextLevelNumres说明初始化101队列 [1]处理根节点 1021左右孩子 2、3 入队层切换203第 2 层有 2 个节点res 1 2处理节点 2113左孩子 4 入队处理节点 3033左孩子 5、右孩子 6 入队层切换306第 3 层有 3 个节点res 3 3处理 4、5、6006叶子节点无孩子队列清空最终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 -covermodeatomic -coverprofilecoverage.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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 222：完全二叉树节点计数 —— LeetCode-Go 仓库 BFS 层序统计解法全解析
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整体策略可以概括为三步空树特判根节点为nil时直接返回 0按层遍历借助队列做广度优先遍历同时维护当前层剩余待处理节点数与下一层节点数两个计数器逐层累加每当一层处理完毕就把下一层的节点数累加到结果中直至队列为空。这种做法的正确性不依赖完全二叉树这一特殊性质——它对任意二叉树都成立因此实现简单、不易出错代价是要访问全部节点。源码逐段解析仓库中的解法完整代码如下为便于理解此处按逻辑分段说明实际文件即 222. Count Complete Tree Nodes.gofunc 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 控制当前层的处理节奏每次从队首取出一个节点queue[0]若其左孩子存在入队并让nextLevelNum右孩子同理处理完当前节点后curNum--并弹出队首元素queue queue[1:]当curNum减到 0说明当前层已全部处理完毕此时把nextLevelNum下一层节点数累加到res并让curNum nextLevelNum、nextLevelNum 0进入下一轮循环处理新的一层。以题目示例手工推演对示例树[1, 2, 3, 4, 5, 6]的推演过程如下阶段curNumnextLevelNumres说明初始化101队列 [1]处理根节点 1021左右孩子 2、3 入队层切换203第 2 层有 2 个节点res 1 2处理节点 2113左孩子 4 入队处理节点 3033左孩子 5、右孩子 6 入队层切换306第 3 层有 3 个节点res 3 3处理 4、5、6006叶子节点无孩子队列清空最终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 -covermodeatomic -coverprofilecoverage.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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考