> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/222.-count-complete-tree-nodes.md).

# 222. Count Complete Tree Nodes

## 1.問題

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

![](/files/-LSF5V4ub4_QJ52KbH6Z)

##  2.想法 

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

## 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;
    }
};
```