LeetCode222：完全二叉树节点的数量

题目描述
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

解题思路
使用常规二叉树的思想，直接遍历二叉树

代码
递归的两种实现方式

class Solution {
public:
    int getNodeSum(TreeNode* node, int& sum) {
        if (node == nullptr) return 0;
        ++sum;
        getNodeSum(node->left, sum);
        getNodeSum(node->right, sum);
        return sum;

    }
    int countNodes(TreeNode* root) {
        int sum = 0;
        return getNodeSum(root, sum);
    }
};

class Solution {
public:
    int getNodeSum(TreeNode* node) {
        if (node == nullptr) return 0;
       
        int l = getNodeSum(node->left);
        int r = getNodeSum(node->right);
        int treeNum = 1 + l + r;
        return treeNum;

    }
    int countNodes(TreeNode* root) {
        return getNodeSum(root);
    }
};

使用完全二叉树的性质

class Solution {
public:

    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        int leftDepth = 0, rightDepth = 0;
        TreeNode* left = root->left, * right = root->right;
        while (left) {
            leftDepth++;
            left = left->left;
        }

        while (right) {
            rightDepth++;
            right = right->right;
        }
        //如果为满二叉树
        if (leftDepth == rightDepth)
            return (2 << leftDepth) - 1;

        return countNodes(root->left) + countNodes(root->right) + 1;
            
    }
};