☆打卡算法☆LeetCode 222. 完全二叉树的节点个数算法解析

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一颗二叉树，求出该树的节点个数。”

题目链接：

来源：力扣（LeetCode）

链接： 222. 完全二叉树的节点个数 - 力扣（LeetCode）

2、题目描述

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

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

代码语言：javascript复制

示例 1：
输入： root = [1,2,3,4,5,6]
输出： 6

代码语言：javascript复制

示例 2：
输入： root = []
输出： 0

二、解题

1、思路分析

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

对于任意二叉树，都可以通过广度优先搜索算法BFS计算节点个数，这道题给定的完全二叉树，可以使用完全二叉树的特点计算节点个数。

完全二叉树的特性可知，最左边的节点一定位于最底层，从根节点出发，每次访问左子节点，直到遇到叶子结点，该叶子结点即为完全二叉树的最左边的节点，经过的路径啊成都为最大层数h。

第i层包含2i个节点，最底层包含的节点数最少为1，最多为2h。

因此对于最大层数为h的完全二叉树，可以通过二分查找的方式得到完全二叉树的节点个数。

根据节点的个数范围判断得到节点个数k：

如果第k个节点存在，则节点个数一定大于或等于k
如果第k个节点不存在，可以将查找的范围缩小一半，直到得到节点个数

2、代码实现

代码参考：

代码语言：javascript复制

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 &amp;&amp; bits > 0) {
            if ((bits &amp; k) == 0) {
                node = node.left;
            } else {
                node = node.right;
            }
            bits >>= 1;
        }
        return node != null;
    }
}