leetcode：222完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 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：题目分析

问题性质：

本问题要求计算给定完全二叉树的节点数。

输入条件：

• 树的根节点 root。
• 树是完全二叉树（完全二叉树定义见题目）。

输出条件：

• 返回完全二叉树的节点个数。

限制条件：

1. 树中节点的范围是 [0, 5 * 10^4]。
2. 节点值范围是 [0, 5 * 10^4]。
3. 完全二叉树性质：
   • 除了最底层，其余层的节点数达到最大值。
   • 最底层节点集中在最左侧。

边界条件：

1. 树为空（root = []）。
2. 树只有一个节点。
3. 树的最底层部分节点缺失，但仍满足完全二叉树性质。

步骤2：解题思路

方法1：朴素解法（时间复杂度 O(n)）

• 思想：遍历整个树，统计所有节点数量。
• 实现方式：使用递归或迭代方式实现树的遍历。
• 时间复杂度：O(n)，因为需要访问每个节点。
• 缺点：没有利用完全二叉树的性质优化。

方法2：利用完全二叉树性质（时间复杂度 O(log²n)）

• 思想：完全二叉树的性质可以帮助我们快速计算节点个数：
  1. 若树是满二叉树（所有节点都填满），节点总数为 2^h - 1，其中 h 是树的深度。
  2. 如果树不是满二叉树，可以递归地判断左右子树：
     • 通过计算左右子树的高度，判断左子树是否是满二叉树：
       • 若左子树高度等于右子树高度，则左子树为满二叉树，节点数为 2^h - 1。
       • 否则，递归到右子树进行计算。
• 时间复杂度：
  • 对于完全二叉树，树的深度为 O(logn)，递归每次减少一半的节点。
  • 每次递归需要计算树的高度（O(logn)）。
  • 总时间复杂度：O(log²n)。
• 空间复杂度：O(logn)（递归栈深度）。

步骤3：C++代码实现

代码注释说明：

1. computeDepth 函数：
   • 计算完全二叉树的深度，只需沿着左子树遍历即可，时间复杂度 O(logn)。
2. countNodes 函数：
   • 递归判断左右子树是否为满二叉树。
   • 若是满二叉树，直接通过公式计算节点数量，无需遍历。
   • 若不是，递归到子树继续判断。

步骤4：解决问题的启发

1. 利用特定数据结构的性质：
   • 本题通过完全二叉树的特殊性质大幅优化节点统计效率。设计高效算法时，理解数据结构的特性是关键。
2. 数学与递归的结合：
   • 使用数学公式（满二叉树节点数公式）结合递归分治法，解决问题的效率远高于直接遍历。
3. 时间复杂度的改进：
   • 从 O(n) 优化到 O(log²n)，体现了算法优化的重要性。

步骤5：算法在实际生活中的应用

实际应用场景：数据库索引结构

完全二叉树的性质和节点统计方法可用于数据库索引优化：

1. 场景：
   • 数据库的 B+ 树索引结构中，节点数量可以通过类似的递归计算方法快速统计。
   • 例如，统计某个范围内的数据条目数量。
2. 实现方法：
   • 利用 B+ 树的分层结构和满二叉树性质，通过计算左子树和右子树的深度快速确定数据范围的节点数量。

实际示例：文件系统节点统计

文件系统中，完全二叉树常用于模拟目录和文件的结构。计算某个子目录下的文件总数时，可以采用类似的递归计算方法，快速得出结果，而无需遍历整个目录结构。