完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。
方法一：直接使用普适的求二叉树节点个数解法
递归：
class Solution {
public:int countNodes(TreeNode* root) {if(root == nullptr) return 0;int leftnum = countNodes(root->left);int rightnum = countNodes(root->right);int num = leftnum + rightnum + 1;return num;}
};迭代：
class Solution {
public:int countNodes(TreeNode* root) {if(root == nullptr) return 0;queue<TreeNode*> q;q.push(root);int num = 0;while(!q.empty()){int size = q.size();for(int i = 0; i < size; i++){TreeNode* cur = q.front();q.pop();num++;if(cur->left) q.push(cur->left);if(cur->right) q.push(cur->right);}}return num;}
};方法二：利用二叉树性质（更高效）
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。
这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？
在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。
class Solution {
public:int countNodes(TreeNode* root) {if(root == nullptr) return 0;TreeNode* left = root;TreeNode* right = root;int leftheight = 0, rightheight = 0;while(left){leftheight++;left = left->left;}while(right){rightheight++;right = right->right;}if(leftheight == rightheight) return (1 << leftheight) - 1;return 1 + countNodes(root->left) + countNodes(root->right);}
};在代码 return (1 << leftheight) - 1; 中，1 << leftheight 是一个位运算表达式，表示计算 2的leftheight次幂。
1的二进制00000001
比如左移一位变为00000010就是2
左移2位变为00000100就是4
故就可以表示2的leftheight次方。
方法三：二分法
-
计算树的深度
d 完全二叉树的深度由最左路径决定，d 是最后一层的高度（从 0 开始计数）。-
一直向左遍历，直到叶子节点，统计深度。
-
例如，
[1,2,3,4,5,6]的深度d = 2（从1 → 2 → 4，共 3 层，但d是最后一层的高度，这里需根据实现调整）。
-
-
二分查找最后一层的节点数
-
最后一层的节点编号为
1到2^d（例如d=2时编号1~4）。 -
通过二分法检查某个编号的节点是否存在：
-
如果存在，向右搜索（说明右侧可能还有更多节点）。
-
如果不存在，向左搜索（说明该节点及右侧不存在）。
-
-
-
计算总节点数
-
前
d层是满二叉树，节点数为2^d - 1。 -
最后一层的节点数为二分找到的最后一个存在的编号
left。 -
总节点数 = (2^d - 1) + left。
-
class Solution {
private:int getdepth(TreeNode* root){int depth = 0;while(root->left){depth++;root = root->left;}return depth;}bool exist(TreeNode* root, int d, int idx){int left = 0, right = (1 << d) - 1;for(int i = 0; i < d; ++i){int mid = left + (right - left) / 2;if(idx <= mid){root = root->left;right = mid;}if(idx > mid){root = root->right;left = mid + 1;}}return root != nullptr;}public:int countNodes(TreeNode* root) {if (!root) return 0;int d = getdepth(root); if (d == 0) return 1;int left = 1, right = (1 << d);while (left < right) {int mid = left + (right - left) / 2;if (exist(root, d, mid)) {left = mid + 1;} else {right = mid;}}return (1 << d) - 1 + left;}
};-
exists函数的任务：给定一个编号idx，判断它在完全二叉树的最后一层是否存在。 -
如何判断：
-
从根节点出发，按照
idx的二进制位决定路径（0=左，1=右）。 -
走完
d步后，检查最终到达的节点是否为空：-
如果
node != nullptr，说明该节点存在。 -
如果
node == nullptr，说明该节点不存在。
-
-
if (exists(root, d, mid))
-
含义：检查编号为
mid的节点是否存在。 -
如果存在 (
true)：-
说明
mid及所有比它小的节点都存在。 -
我们需要尝试更大的编号，因此调整左边界：
-
逻辑：既然
mid存在，最后一个存在的节点可能在[mid + 1, right]范围内。
-
-
如果不存在 (
false)：-
说明
mid节点缺失，且所有比它大的节点也一定缺失（因为完全二叉树的最后一层从左到右连续排列）。 -
我们需要尝试更小的编号，因此调整右边界
-
逻辑：最后一个存在的节点可能在
[left, mid - 1]范围内。
-