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

满二叉树的定义如下：二叉树除了叶结点外所有节点都有两个子节点。是完全二叉树的特例。

输入：root = [1,2,3,4,5,6]
输出：6

思路一：层序遍历递归

1. 递归法

class Solution {
private:int getNodeNum(TreeNode* cur) {if (cur == 0) return 0;int leftNum = getNodesNum(cur->left); // 左int rightNum = getNodesNum(cur->right); // 右int treeNum = leftNum + rightNum + 1; // 中return treeNum;}
public:int countNodes(TreeNode* root){return getNodeNum(root);}
};

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(logn)，递归系统栈占用的空间

2. 迭代法

class Solution {
public:int countNodes(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);int result = 0;while (!que.empty()) {int size = que.size();for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();result++;   // 记录节点数量if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return result;}
};

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

思路二：完全二叉树

完全二叉树只有两种情况：

• case1：满二叉树
• case2：最后一层叶子节点没有满

1. 对于case1，可以直接用2^树深度-1来计算，根节点深度为1
2. 对于case2，分别递归左孩子和右孩子，递归到某一深度，一定会有左孩子或者右孩子为满二叉树。

class Solution {
public:int countNodes(TreeNode* root) {if (root == nullptr) return 0;TreeNode* left = root->left;TreeNode* right = root->right;int leftHeight = 0, rightHeight = 0; // 这里初始为0是有目的的，为了下面求指数方便while (left) {  // 求左子树深度left = left->left;leftHeight++;}while (right) { // 求右子树深度right = right->right;rightHeight++;}if (leftHeight == rightHeight) {return (2 << leftHeight) - 1; // 注意(2<<1) 相当于2^2，所以leftHeight初始为0}return countNodes(root->left) + countNodes(root->right) + 1;}
};

时间复杂度：O(logn * logn)
空间复杂度：O(logn)