完全二叉樹?的定義如下：在完全二叉樹中，除了最底層節點可能沒填滿外，其余每層節點數都達到最大值，并且最下面一層的節點都集中在該層最左邊的若干位置。若最底層為第?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次方。

方法三：二分法

1. 計算樹的深度?d?完全二叉樹的深度由最左路徑決定，d 是最后一層的高度（從 0 開始計數）。

   • 一直向左遍歷，直到葉子節點，統計深度。

   • 例如，[1,2,3,4,5,6]?的深度?d = 2（從?1 → 2 → 4，共 3 層，但?d?是最后一層的高度，這里需根據實現調整）。

2. 二分查找最后一層的節點數

   • 最后一層的節點編號為?1?到?2^d（例如?d=2?時編號?1~4）。

   • 通過二分法檢查某個編號的節點是否存在：

     • 如果存在，向右搜索（說明右側可能還有更多節點）。

     • 如果不存在，向左搜索（說明該節點及右側不存在）。

3. 計算總節點數

   • 前?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，判斷它在完全二叉樹的最后一層是否存在。

• 如何判斷：

  1. 從根節點出發，按照?idx?的二進制位決定路徑（0=左，1=右）。

  2. 走完?d?步后，檢查最終到達的節點是否為空：

     • 如果?node != nullptr，說明該節點存在。

     • 如果?node == nullptr，說明該節點不存在。

if (exists(root, d, mid))

• 含義：檢查編號為?mid?的節點是否存在。

• 如果存在 (true)：

  • 說明?mid?及所有比它小的節點都存在。

  • 我們需要嘗試更大的編號，因此調整左邊界：

  • 邏輯：既然?mid?存在，最后一個存在的節點可能在?[mid + 1, right]?范圍內。

• 如果不存在 (false)：

  • 說明?mid?節點缺失，且所有比它大的節點也一定缺失（因為完全二叉樹的最后一層從左到右連續排列）。

  • 我們需要嘗試更小的編號，因此調整右邊界

  • 邏輯：最后一個存在的節點可能在?[left, mid - 1]?范圍內。