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

朱雀 2023-10-15 21:18 51阅读 0赞

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

*  1. 题目描述
 *  2. 解题思路
 *   *  2.1 普通二叉树
     *   *  2.1.1 递归
         *   *  2.1.1.1 确定递归函数的参数和返回值
             *  2.1.1.2 确定终止条件
             *  2.1.1.3 确定单层递归的逻辑
         *  2.1.2 迭代
 *  3. 完全二叉树
 *  4. 代码实现
 *   *  4.1 通用递归解法
     *  4.2 迭代法
     *  4.3 针对完全二叉树的解法

# 1. 题目描述 #

[力扣入口-222.完全二叉树的节点个数][-222.]

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

示例 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  
题目数据保证输入的树是 完全二叉树

# 2. 解题思路 #

给出两种解题方法：

1.  使用普通二叉树的求法
2.  利用完全二叉树性质

## 2.1 普通二叉树 ##

递归法和求二叉树的深度写法类似，依然是后序遍历的方法。

迭代法也是通过记录遍历节点来统计数量。

### 2.1.1 递归 ###

#### 2.1.1.1 确定递归函数的参数和返回值 ####

参数就是传入树的根节点，返回就返回以该节点为根节点二叉树的节点数量，所以返回值为int类型。

代码如下：

int getNodesNum(TreeNode* cur){

#### 2.1.1.2 确定终止条件 ####

如果为空节点的话，就返回0，表示节点数为0。

代码如下 :

if(cur == NULL) return 0;

#### 2.1.1.3 确定单层递归的逻辑 ####

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

代码如下：

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

时间复杂度：O(n)  
空间复杂度：O(log n)，算上了递归系统栈占用的空间。

### 2.1.2 迭代 ###

时间复杂度：O（n）  
空间复杂度：O（n）

# 3. 完全二叉树 #

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

举例说明：  
![在这里插入图片描述][ca4be70312954f1aa13978ab1b09c910.png]  
完全二叉树只有两种情况：  
情况一：满二叉树  
情况二：最后一层叶子节点没有满

对于情况一，可以直接用2^树深度- 1来计算，注意这里根节点深度为1。

对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

完全二叉树（一）如图：  
![在这里插入图片描述][b4469a6ef51c4fc1a554d0c92b8c6fa5.png]  
完全二叉树（二）如图：  
![在这里插入图片描述][19ac9cdab934475285cfa09821d6e04a.png]  
可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。

这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？

在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。如图：  
![在这里插入图片描述][ffb438cd51204ef08cb57e52aa4fca1a.png]  
在完全二叉树中，如果递归向左遍历的深度不等于递归向右遍历的深度，则说明不是满二叉树，如图：  
![在这里插入图片描述][e857dbb116694e2da0cb59f0cd0a1991.png]  
另一种不是满二叉树的情况如图所示，递归向左遍历的深度等于递归向右遍历的深度，但也不是满二叉树：  
![在这里插入图片描述][f365305f9f86433cabd50313924fad31.png]  
以上的理解是有误区的，以上这颗二叉树**根本就不是一个完全二叉树**。

# 4. 代码实现 #

## 4.1 通用递归解法 ##

public int countNodes(TreeNode root){
        
        if(root == null){
        
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }

## 4.2 迭代法 ##

public int countNodes2(TreeNode root){
        
        if(root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int result = 0;
        while(!queue.isEmpty()){
        
            int size = queue.size();
            while(size-- > 0){
        
                TreeNode cur = queue.poll();
                result++;
                if(cur.left != null) queue.offer(cur.left);
                if(cur.right != null) queue.offer(cur.right);
            }
        }
        return result;
    }

## 4.3 针对完全二叉树的解法 ##

public int countNodes3(TreeNode root){
        
        if(root == null) return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的, 为了下面求指数方便
        while(left != null){
         // 求左子树深度
            left = left.left;
            leftDepth++;
        }
        while(right != null){
         // 求右子树深度
            right = right.right;
            rightDepth++;
        }
        if(leftDepth == rightDepth){
        
            return (2 << leftDepth) - 1; // 注意(2<<1)相当于2^2, 所以leftDepth初始为0
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }

**参考资料**：[代码随想录-222.完全二叉树的节点个数][-222. 1]

[-222.]: https://leetcode.cn/problems/count-complete-tree-nodes/
[ca4be70312954f1aa13978ab1b09c910.png]: https://img-blog.csdnimg.cn/ca4be70312954f1aa13978ab1b09c910.png
[b4469a6ef51c4fc1a554d0c92b8c6fa5.png]: https://img-blog.csdnimg.cn/b4469a6ef51c4fc1a554d0c92b8c6fa5.png
[19ac9cdab934475285cfa09821d6e04a.png]: https://img-blog.csdnimg.cn/19ac9cdab934475285cfa09821d6e04a.png
[ffb438cd51204ef08cb57e52aa4fca1a.png]: https://img-blog.csdnimg.cn/ffb438cd51204ef08cb57e52aa4fca1a.png
[e857dbb116694e2da0cb59f0cd0a1991.png]: https://img-blog.csdnimg.cn/e857dbb116694e2da0cb59f0cd0a1991.png
[f365305f9f86433cabd50313924fad31.png]: https://img-blog.csdnimg.cn/f365305f9f86433cabd50313924fad31.png
[-222. 1]: https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE