题解 | #完全二叉树结点数#

/**
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    int rootHeight(TreeNode* root, int height) {
        if(!root)
            return height;
        int left = rootHeight(root->left, height + 1);
        return left;
    }
    int nodeNum(struct TreeNode* head) {
        if(!head)
            return 0;
        // 计算左右子树的高度
        int l = rootHeight(head->left, 0);
        int r = rootHeight(head->right, 0);
        if(l == r)
            // 如果左右子树相等，则证明根节点左子树为完全二叉树
            // 则计算右子树的节点数在加上 左子树的节点总数+根节点（2^l）
            return nodeNum(head->right) + (1 << l);
        else
            return nodeNum(head->left) + (1 << r);
    }
};