# 222. Count Complete Tree Nodes

## problem description

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

**Example:**

```
Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6
```

## algorithm thought

第一次做这个题的时候，直接没考虑这是个完全二叉树，直接写了个计算二叉树节点数量的函数，直接提交，对了就没管了。

这次做的时候，觉得肯定有更好的办法，因为完全二叉树和普通二叉树相比，多了太多信息。

这里用递归结题，我们知道，计算一个完美二叉树（忘了具体是啥名字了，就是最后一层都是NULL，其他节点都不为NULL）的节点数量很简单，如果有h层，结果就是2^h-1。对于一个完全二叉树，他左子树和右子树肯定有一个是完美二叉树，只要找到这个完美二叉树，就可以直接计算出结果，然后对另一个子树递归调用这个函数。直到节点为NULL

## code

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        int h=height(root);
        return h==-1?0:
            height(root->right)==h-1?(1<<h)+countNodes(root->right):
                                        (1<<(h-1))+countNodes(root->left);
    }
    int height(TreeNode* root){
        return root==NULL?-1:height(root->left)+1;  //由于保证是完全二叉树，所以计算高度直接在左边即可
    }
};
```

## algorithm analysis

这个时间复杂度是O(lgn\*lgn)，具体时间复杂度分析如下

```
T(n) = T(n/2) + c1 lgn
       = T(n/4) + c1 lgn + c2 (lgn - 1)
       = ...
       = T(1) + c [lgn + (lgn-1) + (lgn-2) + ... + 1]
       = O(lgn*lgn)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kongchengzhuge.gitbook.io/leetcode/222.-count-complete-tree-nodes.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.