题目链接:https://leetcode.cn/problems/count-complete-tree-nodes/description/
题目叙述
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6
示例 2：
输入：root = []
输出：0
示例 3：
输入：root = [1]
输出：1
提示：
树中节点的数目范围是[0, 5 * 10 ^4]
0 <= Node.val <= 5 * 10^4
题目数据保证输入的树是 完全二叉树
思路
这题可以使用递归的方法和迭代的方法，两种都是可以的。并且这道题使用前序，中序，或者后序的遍历顺序都是可以做出来的，这题并没有限制我们的遍历顺序，下面我会讲解递归法和迭代法
递归法
递归要确定的有三个条件
- 递归函数的传入参数和返回值，这题明显我们需要传入一个树的根节点
root,并且要返回一个int类型的值。 - 递归函数的结束条件，这题明显我们遍历到空节点的时候，我们就需要返回了。因此，递归的结束条件为：
if (root == NULL) return 0; - 单层递归的逻辑：我们这道题，是要求所有节点的个数，我们可以拆解为左子树的节点个数+右子树的节点个数+根节点(1)。因此，我们可以对这个步骤拆分，对左子树的左右子树做同样的事情，调用同样的
函数，这就是单层递归的逻辑，对不同的对象使用相同的条件。
通过上面的分析，我们很快就可以得出递归法的代码：
//递归法求完全二叉树的节点个数
class Solution {
public:
int countNodes(TreeNode* root) {
//碰到空节点，我们就返回
if (root == NULL) return 0;
//递归求左子树的节点个数
int leftCount = countNodes(root->left);
//递归求右子树的节点个数
int rightCount = countNodes(root->right);
//总节点个数等于左节点个数加右节点的个数
return leftCount + rightCount + 1;
}
};
其实，递归法的代码能够非常简结，不过这样就看不出来我们分析的过程了，需要的读者可以自行选择哪一种的代码
//递归法求完全二叉树的节点个数
class Solution {
public:
int countNodes(TreeNode* root) {
//碰到空节点，我们就返回
if (root == NULL) return 0;
//总节点个数等于左节点个数加右节点的个数
return countNodes(root->left)+countNodes(root->right) + 1;
}
};
迭代法
这题使用递归法是最简单的做法，不过其实我们也可以使用迭代法来一个一个数节点的个数，其实递归的本质就是穷举，我们迭代法只不过是将暴力枚举的过程形象表示出来了而已
- 迭代法的前序遍历
我们在使用栈来模拟前序遍历时，只需要一个count变量，每一次出栈的时候，代表着有一个节点处理完了，我们让这个count变量自增一次即可
//前序遍历求完全二叉树的节点个数
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == NULL) return 0;
stack<TreeNode*> st;
st.push(root);
//设置count变量来计数
int count = 0;
while (!st.empty()) {
TreeNode* cur = st.top();
st.pop();
//出栈一次我们就自增一次
count++;
//先放右孩子，因为栈是一种后进先出的结构（不过这里先后处理其实无所谓，因为节点个数和遍历顺序无关）
if (cur->right != NULL) st.push(cur->right);
if (cur->left != NULL) st.push(cur->left);
}
return count;
}
};
- 中序遍历，中序遍历其实和前序遍历差不多是一样的道理，每出栈一次我们就让
count自增一次即可
//中序遍历求完全二叉树的节点个数
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == NULL) return 0;
stack<TreeNode*> st;
TreeNode* cur = root;
//设置count变量
int count = 0;
while (cur != NULL || !st.empty()) {
if (cur != NULL) {
st.push(cur);
cur = cur->left;
}
else {
cur = st.top();
st.pop();
//出栈一次就自增一次
count++;
cur = cur->right;
}
}
return count;
}
};
- 层序遍历，这题使用层序遍历也是可以的，只不过就是栈换成了队列，出队一次我们就自增一次
count
//层序遍历求完全二叉树的节点个数
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == NULL) return 0;
queue<TreeNode*> que;
que.push(root);
//定义count遍历
int count = 0;
while (!que.empty()) {
int size = que.size();
while (size--) {
TreeNode* cur = que.front();
que.pop();
//出队一次就自增一次
count++;
if (cur->left != NULL) que.push(cur->left);
if (cur->right != NULL) que.push(cur->right);
}
}
return count;
}
};