# Count Complete Tree Nodes

<https://leetcode.com/problems/count-complete-tree-nodes/description/>

> Given a complete binary tree, count the number of nodes.
>
> 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.

## Thoughts

<https://discuss.leetcode.com/topic/15515/easy-short-c-recursive-solution/4>

这道题本来想用二分法做，实现非常复杂还超时。后来看到别人的解法，可以看作是分治版本的改进，利用完全二叉树的性质，计算最左和最右的深度，如果深度相同代表是满的，直接返回；不同则调用原分治算法

## Code

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int leftHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return leftHeight(root.left) + 1;
    }

    private int rightHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return rightHeight(root.right) + 1;
    }

    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = leftHeight(root);
        int right = rightHeight(root);
        if (left == right) {
            return (1 << left) - 1; 
        } else {
            return countNodes(root.left) + countNodes(root.right) + 1;
        }
    }
}
```

## Analysis

画个树能看出当不满时，会对不满的那条path走下去(O(h))，由于每一步需要O(h)算深度，总O(h^2).

参照分析

[morrischen2008](https://discuss.leetcode.com/user/morrischen2008)

Let n be the total number of the tree. It is likely that you will get a child tree as a perfect binary tree and a non-perfect binary tree (T(n/2)) at each level.

```
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)
```

每次有一半树是perfect tree. 下一次深度是上次深度减一, 因此是logn-1,不是lg(n-1).

`(lgn)! = Θ((lgn)^(lgn) + 0.5e^(-lgn) )`

```
lg(n!) = Θ(nlgn)
```

## Ver.2

<https://leetcode.com/problems/count-complete-tree-nodes/discuss/61958>

把高度定义为一直顺着左节点走能走的**边**个数. 算出当前节点左儿子和右儿子的高度, 当它们高度相同时, 意味着左子树是full tree，右边可能有空缺，把左子树的count算上; 否则右子树是full tree，同理。 一共lgN步, 每步算高度花费lgN, 因此lgN \* lgN。

```
/**
 * 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) {
        const auto height = [&](TreeNode *cur) {
            int h = 0;
            while (cur != NULL) {
                cur = cur->left;
                ++h;
            }
            return h;
        };
        auto cur = root;
        int res = 0;
        while (cur != NULL) {
            int l = height(cur->left);
            int r = height(cur->right);
            if (l == r) {
                // left is a full tree: count = 2 ^ h - 1 + 1
                res += 1 << l;
                cur = cur->right;
            } else {
                // right is a full tree: 2 ^ r - 1 + 1
                res += 1 << r;
                cur = cur->left;
            }
        }
        return res;
    }
};
```


---

# 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://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/divide-and-concquer/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.