# 222     Count Complete Tree Nodes

## 222. [Count Complete Tree Nodes](https://leetcode.com/problems/count-complete-tree-nodes/description/)

## 1. Question

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

**Definition of a complete binary tree from**[**Wikipedia**](https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees)**:**\
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 2hnodes inclusive at the last level h.

## 2. Implementation

**(1) Method 1**

思路: 对于每个node，找出最左边和最右边的高度，如果这两个高度相同，说明这个树是完美二叉树，其node的数目等于 2^height - 1。如果这两个高度不同，递归地检测它的左子树和右子树是否完美二叉树，是的话就可以直接用公式计算, node数目等于它这个node加上左子树的node和右子树的node

```java
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftMostHeight = getHeight(root, true);
        int rightMostHeight = getHeight(root, false);

        if (leftMostHeight == rightMostHeight) {
            return (1 << leftMostHeight) - 1;
        }

        return 1 + countNodes(root.left) + countNodes(root.right);
    }

    public int getHeight(TreeNode node, boolean isLeft) {
        int height = 0;

        while (node != null) {
            if (isLeft) {
                node = node.left;
            }
            else {
                node = node.right;
            }
            ++height;
        }
        return height;
    }
}
```

**(2) Method 2: 二分法**

思路：根据Complete tree的leaf node as far left as possible的特点，对一个节点的左子树和右子树，我们分别找出最左的深度。如两边最左深度相同，说明左子树是完美二叉树，可以直接用公式计算node个数，否则右边子树的高度肯定小于左边子树，而且右边子树根据complete的特点也必然是完美二叉树，用公式计算其node个个数。这样就可以达到二分的效果

```java
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int count = 1;

        int leftHeight = getLeftMostHeight(root.left);
        int rightHeight = getLeftMostHeight(root.right);

        if (leftHeight == rightHeight) {
            count += (1 << leftHeight) - 1;
            count += countNodes(root.right);
        }
        else {
            count += (1 << rightHeight) - 1;
            count += countNodes(root.left);
        }
        return count;
    }

    public int getLeftMostHeight(TreeNode node) {
        int height = 0;
        while (node != null) {
            node = node.left;
            ++height;
        }
        return height;
    }
}
```

## 3. Time & Space Complexity

Method 1: **时间复杂度 O(h^2)**, 解析: 最坏的情况是每个子树都不是完美二叉树，所以对于每个node，都要花2h的时间去找出它的左子树和右子树的高度，总的时间为 2h + 2(h-1) + 2(h-2) +. ... + 2 => O(h^2), **空间复杂度O(h)**

Method 2: 时间复杂度: O(h^2), 空间复杂度O(h)

## 4. References

<http://blog.csdn.net/jmspan/article/details/51056085>


---

# 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://protegejj.gitbook.io/oj-practices/chapter1/tree/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.