题解 | 完全二叉树结点数

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head TreeNode类
     * @return int整型
     */
    int nodeNum(TreeNode* head) {
        // write code here
        if (!head) return 0;
        int lh = leftHeight(head), rh = rightHeight(head);
        if (lh == rh) {
            // 满二叉树：2^h - 1
            return (1 << lh) - 1;
        }
        // 非满：递归左右子树
        return 1 + nodeNum(head->left) + nodeNum(head->right);
    }
    int leftHeight(TreeNode* node) {
        int h = 0;
        while (node) {
            ++h;
            node = node->left;
        }
        return h;
    }
    int rightHeight(TreeNode* node) {
        int h = 0;
        while (node) {
            ++h;
            node = node->right;
        }
        return h;
    }
};