【二叉树】完全二叉树结点个数

解题思路：递归解决

1.递归结束条件：传入结点为NULL

2.进入左子树和右子树，返回左子树右子树结点个数+1

int countNodes(struct TreeNode* root){
    if(!root)
        return 0;
    return countNodes(root->left) + countNodes(root->right) + 1;
}

解题思路：完全二叉树特性

1.若一棵树为完全二叉树，则其某些子树必满足满二叉树特性

2.因此，通过总结点数=2^深度-1便可得出满二叉子树中结点总数

3.如果左右子树深度不相等，则进入左右子树的左右子树进行比较

int countNodes(struct TreeNode* root){
    if(!root)
        return 0;
    struct TreeNode* left = root->left;
    struct TreeNode* right = root->right;
    int lHeight = 0;
    int rHeight = 0;

    //计算左子树深度
    while(left) {
        left = left->left;
        lHeight++;
    }

    //计算右子树深度
    while(right) {
        right = right->right;
        rHeight++;
    }

    if(lHeight == rHeight) {
        return (2 << lHeight) - 1;
    }
    return countNodes(root->left) + countNodes(root->right) + 1;
}