1、题目描述
给出一个完全二叉树，求出该树的节点个数。
说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例:
image.png
2、思路
对于满二叉树来说，假定高度为N；则它的节点数为2^N - 1。
因而可以将一个完全二叉树分解成若干个满二叉树和完全二叉树。对于完全二叉树用递归求节点数。
3、代码实现（C++）
/**
* 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) {
if (root == nullptr) {
return 0;
}
int left = countLevel(root->left);
int right = countLevel(root->right);
if (left == right) {
// 左右等高，是满二叉树； 递归求右子树节点数，再加上左子树节点数 2^left-1,再加上根节点
return countNodes(root->right) + (1 << left);
}
else {
// 左子树比右子树高，表示右子树是满二叉树，可以直接求节点数，2^right-1,加上根节点；
// 而左子树是完全二叉树，需要递归求解
return countNodes(root->left) + (1 << right);
}
}
// 对于一个完全二叉树而言，树的高度就是左子树的高度+1.
int countLevel(TreeNode* root) {
int level = 0;
while (root != nullptr) {
level++;
root = root->left;
}
return level;
}
};
