零、原题链接

222. 完全二叉树的节点个数

一、题目描述

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

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

二、测试用例

示例 1：

输入：root = [1,2,3,4,5,6]
输出：6

示例 2：

输入：root = []
输出：0

示例 3：

输入：root = [1]
输出：1

提示：

树中节点的数目范围是[0, 5 * 104]
0 <= Node.val <= 5 * 104
题目数据保证输入的树是 完全二叉树

三、解题思路

3.1 递归

1. 基本思路：
     一般是采用遍历所有节点的方法来计算节点个数，既然进阶说有非$\mathrm{O}(n)$的复杂度，那一般是利用满二叉树的性质；在满二叉树中，左右子树树高一样，则左子树为完全满二叉树，即节点数为 $2^h-1$；不一样，则右子树为完全满二叉树；所以可以利用这个性质，不断递归，计算子树节点数。
2. 具体思路：
   • 先计算左右子树树高；
   • 相同，则返回 左子树节点数 + 递归计算右子树节点个数；
   • 不同，则返回 递归计算左子树节点个数 + 右子树节点数；

3.2 二分搜索(非递归）

1. 基本思路：
     根据左右子树树高，不断缩小最后一行最后一个元素所在的位置的范围；
2. 具体思路：
   • 先确定初始范围为：$[0,2^{(h-1)}]$
   • 遍历子树：
     • 左右子树树高相同，最后一个元素在右子树，修改范围下限；
     • 不相同，在左子树，修改范围上限；
   • 总节点数为：树高为 h-1 的完全二叉树的节点数 + 范围上限；

四、参考代码

4.1 递归

时间复杂度：$\mathrm{O}(h^2)$【不断计算子树的树高，即：$1+2+\cdots +h=\frac{h^2+h}{2}$】
空间复杂度：$\mathrm{O}(h^2)$【计算树高其实可以用循环解决，这样空间复杂度就只剩$\mathrm{O}(h)$】

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),* right(right) {}* };*/
class Solution {
public:int countNodes(TreeNode* root) {if (!root)return 0;int lh = countH(root->left);int rh = countH(root->right);if (lh == rh)return pow(2, lh) + countNodes(root->right);elsereturn countNodes(root->left) + pow(2, rh);}int countH(TreeNode* root) {if (!root)return 0;return countH(root->left) + 1;}
};

4.2 二分搜索

时间复杂度：$\mathrm{O}(h^2)$【不断计算子树的树高，即：$1+2+\cdots +h=\frac{h^2+h}{2}$】
空间复杂度：$\mathrm{O}(1)$

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),* right(right) {}* };*/
class Solution {
public:int countNodes(TreeNode* root) {if (!root)return 0;TreeNode* p = root;int l = 0;int r = pow(2, countH(p) - 1) - 1;while (p->left) {if (countH(p->left) == countH(p->right)) {p = p->right;l = (l + r) / 2;} else {p = p->left;r = (l + r) / 2;}}return pow(2, countH(root) - 1) + r;}int countH(TreeNode* root) {int h = 0;for (TreeNode* p = root; p; p = p->left) {h++;}return h;}
};