0222. Count Complete Tree Nodes
===============================
题目信息
--------
:题号: 0222. 完全二叉树的节点个数
:难度: Easy
:主题: 完全二叉树、递归、二分查找、满二叉树
:原题: `LeetCode 0222 `_
:重点: 最后一层左对齐、满子树闭式计数、把线性遍历压到高度平方
题目重述
--------
给定一棵完全二叉树的根节点 ``root``,返回树中的节点个数。完全二叉树除最后一层外每一层都填满;
最后一层的节点全部靠左,层序位置中不会出现空缺后又出现节点。若最后一层编号为 ``h``(根为第 0
层),该层节点数位于 ``[1, 2^h]``。
节点数量位于 ``[0, 5 \times 10^4]``,节点值位于 ``[0, 5 \times 10^4]``。题目保证输入是完全二叉树,
不必再验证结构。统计对象是节点个数,与节点值是否重复无关。空树返回 ``0``;函数只读取指针,
不修改树。进阶要求是设计时间低于 ``O(n)`` 的算法,而不是满足于遍历全部节点。
自建示例
--------
最后一层未填满:
.. code-block:: text
输入:root = [8, 4, 12, 2, 6]
输出:5
解释:层序为根、两个孩子、最后一层两个靠左的节点,共 5 个实际节点。
满二叉树:
.. code-block:: text
输入:root = [8, 4, 12, 2, 6, 10, 14]
输出:7
解释:三层全部填满,节点数为 2^3 - 1 = 7。
单节点与空树:``root = [8]`` 返回 ``1``;``root = []`` 返回 ``0``。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int countNodes(TreeNode* root) {
return countByPerfectSubtree(root);
}
private:
int countByTraversal(TreeNode* node) {
if (node == nullptr) return 0;
return 1 + countByTraversal(node->left) + countByTraversal(node->right);
}
int leftHeight(TreeNode* node) {
int height = 0;
while (node != nullptr) {
++height;
node = node->left;
}
return height;
}
int rightHeight(TreeNode* node) {
int height = 0;
while (node != nullptr) {
++height;
node = node->right;
}
return height;
}
int countByPerfectSubtree(TreeNode* node) {
if (node == nullptr) return 0;
const int left = leftHeight(node);
const int right = rightHeight(node);
if (left == right) {
return static_cast((1LL << left) - 1);
}
return 1 + countByPerfectSubtree(node->left) + countByPerfectSubtree(node->right);
}
bool existsAtIndex(TreeNode* root, int index, int height) {
TreeNode* node = root;
for (int bit = height - 2; bit >= 0; --bit) {
if ((index & (1 << bit)) != 0) {
node = node->right;
} else {
node = node->left;
}
if (node == nullptr) return false;
}
return true;
}
int countByLastLevelSearch(TreeNode* root) {
if (root == nullptr) return 0;
const int height = leftHeight(root);
int low = static_cast(1LL << (height - 1));
int high = static_cast((1LL << height) - 1);
while (low < high) {
const int mid = low + (high - low + 1) / 2;
if (existsAtIndex(root, mid, height)) {
low = mid;
} else {
high = mid - 1;
}
}
return low;
}
};
题解
----
遍历给出原始计数空间
~~~~~~~~~~~~~~~~~~~~
``countByTraversal`` 对每个节点贡献 1,再把左右子树的计数相加。空指针返回 0,因此每个实际节点
恰好被访问一次,空树、单节点和最后一层缺节点都不会漏计或重复计。这是直接执行题意的基线。
节点值不进入计算。真正的代价是访问次数等于 ``n``。完全二叉树的高度只有 ``O(\log n)``,递归栈
也是 ``O(\log n)``,但时间仍随节点数线性增长。进阶要求把这层“看见每个节点”的工作删掉。
完全树只在最后一层不确定
~~~~~~~~~~~~~~~~~~~~~~~~
完全二叉树的前 ``h-1`` 层一定是满的,唯一的未知量是最后一层从左数有多少个节点。满二叉树有闭式:
高度按节点层数计、空树高度为 0 时,高度 ``h`` 的满树节点数为
.. math::
1 + 2 + \cdots + 2^{h-1} = 2^h - 1
下文高度一律按“从当前根沿路径走到空指针所经节点数”计算,与题面里从 0 起算的层编号不是同一个量。
若能在不遍历全部节点的前提下判断当前子树是不是满的,整块满区域就可以用一次位移代替逐个访问。
若不是满的,完全性保证缺口只出现在最后一层的右侧,左右子树仍然都是完全二叉树,问题规模按高度下降。
满子树的左右边界高度相同
~~~~~~~~~~~~~~~~~~~~~~~~
从一个节点沿左孩子走到空指针,经过的节点数是左边界高度;沿右孩子走是右边界高度。对完全二叉树:
* 两高度相等,最后一层已经在该子树内填满,整棵子树是满的,直接返回 ``2^h - 1``;
* 两高度不等,缺口一定在某棵子树里,根贡献 1,再分别处理左右子树。
完全性排除了“内部空洞”:最左、最右路径一样长时,中间不可能缺节点。高度不等时,较高的一侧仍可能
是满的,另一侧才需要继续分解;至多一棵子树不是满的,所以递归不会同时沿两条非满路径走下去。
对 ``[8, 4, 12, 2, 6]``:
.. list-table::
:header-rows: 1
* - 当前根
- 左高
- 右高
- 动作
* - 8
- 3
- 2
- 非满,进入两侧
* - 4
- 2
- 2
- 满树,返回 3
* - 12
- 1
- 1
- 满树,返回 1
根贡献 1,总节点数为 ``1 + 3 + 1 = 5``。节点 2、6 没有被单独访问,它们已经包含在以 4 为根的满树公式里。
最后一层可以按堆下标二分
~~~~~~~~~~~~~~~~~~~~~~~~
同一结构还有另一条实现。把节点按完全二叉树的堆编号:根为 1,左孩子 ``2i``,右孩子 ``2i+1``。
高度 ``h`` 时,节点总数位于 ``[2^{h-1}, 2^h - 1]``。判断编号 ``index`` 是否存在:丢掉二进制最高位
的 1,余下每一位 ``0`` 向左、``1`` 向右,从根走到对应位置,路径长度为 ``h-1``。
``countByLastLevelSearch`` 在这个闭区间上二分最大存在编号。判定函数每次走一条根到叶路径,不保存
整层节点。对上面同一棵树,最后一层候选编号是 4 到 7:4、5 存在,6、7 不存在,二分得到 5,正好是
节点总数。它与满子树公式解决的是同一个未知量,只是把“哪棵子树未满”改写成“最后一个节点的编号”。
代码分析
~~~~~~~~
三个私有计数函数对应三层认识。``countByTraversal`` 保留逐节点相加;``countByPerfectSubtree``
删除满子树内部的访问,只沿左、右脊量高度,高度相等就用 ``(1LL << left) - 1`` 闭合,否则把问题
分给两棵仍完全的子树;``countByLastLevelSearch`` 不再递归分解子树,而是在最后一层的编号区间上
查询存在性。
公共入口调用 ``countByPerfectSubtree``,因为它把完全性直接写成“满则闭式、不满则分解”。位移使用
``1LL``,避免在 ``int`` 中左移后再减一。``existsAtIndex`` 的循环从 ``height-2`` 看到 0:根已经
对应最高位的 1,余下 ``h-1`` 步恰好走到最后一层。二分取上中点 ``low + (high - low + 1) / 2``,
存在则把下界抬到 ``mid``,这样才能收敛到最大存在编号,而不是第一个缺口。
复杂度与边界
~~~~~~~~~~~~
.. list-table::
:header-rows: 1
* - 方法
- 时间复杂度
- 工作空间
- 主要代价
* - 遍历计数
- ``O(n)``
- ``O(\log n)`` 递归栈
- 访问每个节点
* - 满子树捷径
- ``O(\log^2 n)``
- ``O(\log n)`` 递归栈
- 每层两次高度探测,至多一条非满递归链
* - 最后一层二分
- ``O(\log^2 n)``
- ``O(1)`` 额外空间
- ``O(\log n)`` 次存在性判定,每次走 ``O(\log n)`` 步
满子树方法中,单次高度探测与当前高度成正比;非满时只有一棵子树继续递归,递归深度为高度,因此
总时间为 ``O(\log^2 n)``。空树在入口直接返回 0。单节点左右高度都是 1,公式给出 1。节点值从不
参与运算。三种实现都不修改树,主解也不分配与 ``n`` 成正比的容器。