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

我会带着你远行 2023-10-08 16:12 19阅读 0赞

## 1 题目描述 ##

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

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

## 2 题目示例 ##

![在这里插入图片描述][a4bb9b58332f4674b683a82966800d06.png]  
示例 2：  
输入：root = \[\]  
输出：0

示例 3：  
输入：root = \[1\]  
输出：1

## 3 题目提示 ##

树中节点的数目范围是\[0, 5 \* 104\]  
0 <= Node.val <= 5 \* 104  
题目数据保证输入的树是 完全二叉树

## 4 思路 ##

对于任意二叉树，都可以通过广度优先搜索或深度优先搜索计算节点个数，时间复杂度和空间复杂度都是O(n)，其中n是二叉树的节点个数。这道题规定了给出的是完全二叉树，因此可以利用完全二叉树的特性计算节点个数。  
规定根节点位于第0层，完全二叉树的最大层数为h。根据完全二叉树的特性可知，完全二叉树的最左边的节点一定位于最底层，因此从根节点出发，每次访问左子节点，直到遇到叶子节点，该叶子节点即为完全二叉树的最左边的节点，经过的路径长度即为最大层数h。  
![在这里插入图片描述][f56ba8a5f8db4724badc21c3efc136fc.png]  
具体做法是，根据节点个数范围的上下界得到当前需要判断的节点个数k，如果第k个节点存在，则节点个数一定大于或等于k，如果第k个节点不存在，则节点个数一定小于k，由此可以将查找的范围缩小—半，直到得到节点个数。  
如何判断第k个节点是否存在呢?如果第k个节点位于第h层，则k的二进制表示包含h＋1位，其中最高位是1，其余各位从高到低表示从根节点到第k个节点的路径，О表示移动到左子节点，1表示移动到右子节点。通过位运算得到第k个节点对应的路径，判断该路径对应的节点是否存在，即可判断第k个节点是否存在。  
![在这里插入图片描述][fc2b4f507f2c4569870f4acdecb2dfbb.png]

## 5 我的答案 ##

class Solution {
        
        public int countNodes(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            int level = 0;
            TreeNode node = root;
            while (node.left != null) {
        
                level++;
                node = node.left;
            }
            int low = 1 << level, high = (1 << (level + 1)) - 1;
            while (low < high) {
        
                int mid = (high - low + 1) / 2 + low;
                if (exists(root, level, mid)) {
        
                    low = mid;
                } else {
        
                    high = mid - 1;
                }
            }
            return low;
        }
    
        public boolean exists(TreeNode root, int level, int k) {
        
            int bits = 1 << (level - 1);
            TreeNode node = root;
            while (node != null && bits > 0) {
        
                if ((bits & k) == 0) {
        
                    node = node.left;
                } else {
        
                    node = node.right;
                }
                bits >>= 1;
            }
            return node != null;
        }
    }

[a4bb9b58332f4674b683a82966800d06.png]: https://img-blog.csdnimg.cn/a4bb9b58332f4674b683a82966800d06.png
[f56ba8a5f8db4724badc21c3efc136fc.png]: https://img-blog.csdnimg.cn/f56ba8a5f8db4724badc21c3efc136fc.png
[fc2b4f507f2c4569870f4acdecb2dfbb.png]: https://img-blog.csdnimg.cn/fc2b4f507f2c4569870f4acdecb2dfbb.png