222. 完全二叉树的节点个数
难度中等248
给出一个完全二叉树，求出该树的节点个数。
说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例:
输入: 1/ \2 3/ \ /
4 5 6输出: 6解题思路：代码随想录
/**迭代法：层次遍历* Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int countNodes(TreeNode* root) {if(root == nullptr) return 0;queue<TreeNode*> que;que.push(root);int cnt = 0;while(!que.empty()){int size = que.size();cnt += size;for(int i = 0; i<size; i++){TreeNode *node = que.front();que.pop();//cnt++;if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return cnt;}
};/**递归* Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int countNodes(TreeNode* root) {if(root == nullptr) return 0;int left_cnt = countNodes(root->left);int right_cnt = countNodes(root->right);return 1 + (left_cnt + right_cnt);}
};