如果之前两篇二叉树：看看这些树的最大深度 ，二叉树：看看这些树的最小深度 都认真看了的话，这道题目可以分分钟刷掉了，愉快过节！

222.完全二叉树的节点个数

给出一个完全二叉树，求出该树的节点个数。

示例:

思路

这道题目其实没有必要强调是完全二叉树，就是求二叉树节点的个数。

依然可以使用递归法和迭代法来解决。

这道题目的递归法和求二叉树的深度写法类似， 而二叉树：层序遍历登场 模板稍稍修改一下，记录遍历的节点数量就可以了。

递归遍历的顺序依然是后序（左右中）。

递归

如果对求二叉树深度还不熟悉的话，看这篇：二叉树：看看这些树的最大深度 。

确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回以该节点为根节点二叉树的节点数量，所以返回值为int类型。

代码如下：

int getNodesNum(TreeNode* cur) {

确定终止条件：如果为空节点的话，就返回0，表示节点数为0。

代码如下：

if (cur == NULL) return 0;

确定单层递归的逻辑：先求它的左子树的节点数量，再求的右子树的节点数量，最后取总和再加一 （加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。

代码如下：

int leftNum = getNodesNum(cur->left);      // 左int rightNum = getNodesNum(cur->right);    // 右int treeNum = leftNum + rightNum + 1;      // 中return treeNum;

所以整体C++代码如下：

class Solution {private:    int getNodesNum(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 getNodesNum(root);    }};

代码精简之后C++代码如下：

class Solution {public:    int countNodes(TreeNode* root) {        if (root == NULL) return 0;        return 1 + countNodes(root->left) + countNodes(root->right);    }};

迭代法

如果对求二叉树层序遍历还不熟悉的话，看这篇：二叉树：层序遍历登场 ！。

那么只要模板少做改动，加一个变量result，统计节点数量就可以了

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;    }};

总结

这道题目的解法其实我们在二叉树：看看这些树的最大深度 和 二叉树：看看这些树的最小深度 都有提到过了。

一样的分析套路，代码也差不多，估计此时大家最这一类求二叉树节点数量以及求深度应该非常熟练了。

没有做过这道题目的同学可以愉快的刷了它。

-------end-------

我将算法学习相关的资料已经整理到了

Github ：，里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图，可以fork到自己仓库有空看一看一定会有所收获，顺便给一个star支持一下吧！

我是程序员Carl，哈工大师兄，先后在腾讯和百度打杂，这里每天8:35准时推送一道经典算法题目，我选择的每道题目都不是孤立的，而是由浅入深，环环相扣，帮你梳理算法知识脉络，轻松学算法！

@代码随想录 期待你的关注