222. 完全二叉树的节点个数

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