完全二叉树和满二叉树

提到完全二叉树，不得不提满二叉树，满二叉树是每层节点的个数都是最多的，即类似一个等腰三角形。

而完全二叉树是满二叉树最后一层从右往左缺几个节点，因此可以说满二叉树是特殊的完全二叉树。

• 对于一个满二叉树而言，如果我们直到层数（深度），那么一定能确定该树的节点个数

• 对于一个不是满二叉树而言，它的子树可能是满二叉树，利用这个性质，我们递归的来求节点个数

时间复杂度$O((logN)^2)$

AC代码

/**
 * 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) return 0;
        //看当前树的是否是满二叉树
        auto pl = root->left, pr = root->right;
        int l = 1 , r = 1;
        while (pl) l ++ , pl = pl->left;
        while (pr) r ++ , pr = pr->right;
        //满二叉树
        if (l == r) return (1 << l) - 1;
        //非满二叉树
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};