80.完全二叉树的节点个数
题目
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。
示例1:
- 输入：root = [1,2,3,4,5,6]
- 输出：6
示例 2：
- 输入：root = []
- 输出：0
示例 3：
- 输入：root = [1]
- 输出：1
提示：
- 树中节点的数目范围是[0, 5 * 104]
- 0 <= Node.val <= 5 * 104
- 题目数据保证输入的树是 完全二叉树
进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
思路
递归遍历每个节点，总数 = 1 + 左子树节点数 + 右子树节点数。
// 暴力 O(n)，完全没利用完全二叉树性质，面试不加分
fun countNodes(root: TreeNode?): Int {
if (root == null) return 0
return 1 + countNodes(root.left) + countNodes(root.right)
}
进阶:
第 1 步：先想一个特殊情况——满二叉树
如果一棵树是满二叉树（每一层都填满），那节点数根本不用数，有公式：
层数 d 的满二叉树，节点数 = 2^d - 1
比如 3 层的满二叉树：2³ - 1 = 7 个节点。
怎么判断一棵树是满的？ 这里有个特别巧的技巧：
- 从根一路向左走到底，记路径上的节点数为 ld
- 从根一路向右走到底，记路径上的节点数为 rd
如果 ld == rd，这棵树就是满的。
为什么这个判断是对的？因为在完全二叉树里，最左边那条路径一定是最深的。如果最右边那条路径也一样深，说明最后一层从最左排到了最 右，一个不缺，那就是满的。
于是思路就出来了：
▎ 递归。到每个节点先测一下 ld 和 rd： ▎ - 相等 → 这块是满树，直接套公式 2^ld - 1 返回，不再往下走 ▎ - 不相等 → 老实拆成 1 + 左子树 + 右子树，递归处理
第 3 步：为什么这样就变快了
关键在于：完全二叉树的任何一个节点，它的左右两个子树中，至少有一个是满二叉树。
想象最后一层的"断点"（最右边那个节点的位置）。这个断点只会落在左子树或右子树的其中一边，另一边必然是完整无缺的满树，会被公式 秒算掉。
所以递归实际上只沿着"断点所在的那条路"往下走，路径长度是 O(log n)；而每个节点上测 ld、rd 又要 O(log n)。
总复杂度 O(log² n)，比 O(n) 快得多。
/**
* 二叉树节点定义（LeetCode 已提供，这里为了完整性列出）
*/
class TreeNode(var `val`: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}
class Solution {
/**
* 统计完全二叉树的节点个数
* 核心思想：满二叉树可以用公式 2^d - 1 直接秒算，
* 所以递归时先判断"当前这块是不是满的"，是就套公式，不是才继续拆。
*
* 时间复杂度 O(log²n)，空间复杂度 O(log n)（递归栈）
*/
fun countNodes(root: TreeNode?): Int {
// 空树，0 个节点
if (root == null) return 0
// ---- 第 1 步：从当前节点一路向左，量出左侧路径的节点数 ----
var leftNode = root.left
var leftDepth = 1 // 当前节点自己算 1 层
while (leftNode != null) {
leftDepth++
leftNode = leftNode.left // 只往左拐
}
// ---- 第 2 步：从当前节点一路向右，量出右侧路径的节点数 ----
var rightNode = root.right
var rightDepth = 1
while (rightNode != null) {
rightDepth++
rightNode = rightNode.right // 只往右拐
}
// ---- 第 3 步：两侧一样深 → 这是一棵满二叉树，公式直接出结果 ----
// (1 shl d) 就是 2^d，位运算比 Math.pow 更快也不会有浮点误差
if (leftDepth == rightDepth) {
return (1 shl leftDepth) - 1
}
// ---- 第 4 步：不是满树，老实递归左右子树 ----
// 注意：这两个子树里必有一个是满的，会在下一层递归被公式秒算掉，
// 所以真正深入递归的只有一条路，整体不会退化成 O(n)
return 1 + countNodes(root.left) + countNodes(root.right)
}
}
复杂度
- 时间复杂度: O(log² n)
- 空间复杂度: O(log n)
- 邮箱 ：charon.chui@gmail.com
- Good Luck!