本文主要是介绍算法练习第19天|222.完全二叉树的节点个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
222.完全二叉树的节点个数
222. 完全二叉树的节点个数 - 力扣（LeetCode）
https://leetcode.cn/problems/count-complete-tree-nodes/description/
题目描述：
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。题目数据保证输入的树是 完全二叉树
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6] 输出：6
示例 2：
输入：root = [] 输出：0
示例 3：
输入：root = [1] 输出：1
题目分析：
按照前文所讲的二叉树的递归遍历以及层序遍历，可以将完全二叉树看作普通二叉树处理，进行节点个数的统计。思路较为简单，代码如下：
后序递归遍历解法：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public://后序递归,第一步，确定函数参数以及返回值int countNodes(TreeNode* root) { //递归第二步,确定递归终止条件。当递归函数指针root为空，递归终止if(root == nullptr) return 0;//递归第三步，确定单层递归逻辑：统计左右子树的节点个数，然后相加再加1int left = countNodes(root->left); //左int right = countNodes(root->right); //右int result = 1 + left + right; //1就是后序遍历顺序的中 return result;}
};层序遍历解法（也叫迭代法）：
class Solution {
public://层序遍历int countNodes(TreeNode* root) { if(root == nullptr) return 0;queue<TreeNode*> que;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;}
};完全二叉树解法：
但是上述方法都是将完全二叉树当做普通二叉树来进行题目的求解，这样就忽略了完全二叉树的性质。完全二叉树时除了最底层的节点可能不满之外，其余层均是满的，并且，最底层的节点必须是严格从左往右依次排列的，不能有跳跃（如下面的最右侧的二叉树，蓝色框内存在跳跃，所以其不是完全二叉树）。
如果完全二叉树最底层也填满了的话，这时它就也是满二叉树。节点个数为 ，n为二叉树的层数。
所以完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用来计算。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
关键点来了，怎么判断左右孩子是不是满二叉树？在完全二叉树中，如果递归一直向左遍历的深度等于递归一直向右遍历的深度，那说明就是满二叉树。前提是一定要在完全二叉树中。
所以，该解法的递归终止条件如下所示：
if (root == nullptr) return 0;
// 开始根据左深度和右深度是否相同来判断该子树是不是满二叉树
TreeNode* left = root->left;
TreeNode* right = root->right;
int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
while (left) { // 求左子树深度left = left->left;leftDepth++;
}
while (right) { // 求右子树深度right = right->right;rightDepth++;
}
if (leftDepth == rightDepth) {return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，返回满足满二叉树的子树节点数量
}递归三部曲，第三部，单层递归的逻辑：（可以看出使用后序遍历）
int leftTreeNum = countNodes(root->left); // 左
int rightTreeNum = countNodes(root->right); // 右
int result = leftTreeNum + rightTreeNum + 1; // 中
return result;整体代码如下：
class Solution {
public://递归第一步int countNodes(TreeNode* root) { //递归第二步，确定递归终止条件 if(root == nullptr) return 0;TreeNode *left = root->left;TreeNode *right = root->right;int leftDepth=0 , rightDepth = 0;while(left) //一直向左遍历，求深度{leftDepth++;left = left->left;}while(right) //一直向右遍历，求深度{rightDepth++;right = right->right;}if(leftDepth == rightDepth) //当前的完全二叉树为满二叉树return (2 << leftDepth) - 1; //2的n次方减一//递归第三步，确认单层递归逻辑//不然的话，就递归统计左右子树的节点数。每一级递归都会进行上面的满二叉树判断int left = countNodes(root->left); //左int right = countNodes(root->right); //右int result = left + right + 1; //中return result;}
};该解法与后续递归解法的不同之处就在于递归终止条件，该解法核心思想致力于逐子树判断是否为满二叉树。如果是，使用计算节点数；如果不是，则进行下一层的递归countNodes。思路很巧妙。
这篇关于算法练习第19天|222.完全二叉树的节点个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
