# 222. Count Complete Tree Nodes

## 1.問題

* 給予一個complete binary tree, 計算node數量

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LSF4LaSas4ZyZb3ZLjT%2F-LSF5V4ub4_QJ52KbH6Z%2F20181126_2.jpg?alt=media\&token=0e983d42-81ab-404f-a227-7bad39062f3c)

## &#x20;2.想法&#x20;

* complete binary tree: 左右子樹的高度差在1以內, 每個leaf不一定有兩個child, 但會先填左子樹
* full binary tree: 左右子樹的高度差沒有限制, 每個leaf一定有兩個child
* perfect binary tree: 左右子樹的高度差在1以內, 每個leaf一定有兩個child,&#x20;

## 3.程式碼

```
/**
 * 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 left = findLeftDepth(root);
        int right = findRightDepth(root);
        if (left == right) {
            return pow(2, left) - 1;
        } 
        
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
private:
    int findLeftDepth(TreeNode* root) {
        if (!root) {
            return 0;
        }
        
        return findLeftDepth(root->left) + 1;
    }
    
    int findRightDepth(TreeNode* root) {
        if (!root) {
            return 0;
        }
        
        return findRightDepth(root->right) + 1;
    }
};
```
