完全二叉树的节点个数(力扣)

题目分析

要统计二叉树的节点个数，一般是编历一遍二叉树直接统计(可以用后序遍历或者层序遍历，这里就不说了)。

而这个是完全二叉树,我们可以根据完全二叉树的特点进行求解。

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

则可以设完全二叉树有 h 层，则其前h-1的节点都是满的，共有节点 2^(h-1) - 1 个节点。而最后一层最少有 1 个节点，最多有 2^(h-1) 个节点。因此 h 层的完全二叉树的节点个数范围为：[2^(h-1) - 1 + 1, 2^(h-1) - 1 + 2^(h-1)] = [2^(h-1), 2^h - 1]【或 [2^(h-1), 2^h) 】

位运算

我们把每个节点编号转成二进制，可以发现以下几个规律：

第 h 层的节点编号的二进制刚好有 h 位；
定义左子节点为 0，右子节点为 1 。那么每一个节点编号的二进制从高位到低位刚好表示根节点到这个节点的路径。【根节点为最高位，始终为 1】即节点编号的二进制为节点路径的编码；

则可以发现第h层的节点编号一定是有h位。我们可以根据已知的节点走一遍节点路径，来查找这个节点是否存在。

代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) //如果根结点为null，直接返回0
            return 0;
        TreeNode node = root;
        int leavl = 0;
        while(node != null){    //统计完全二叉树的层数
            leavl++;
            node = node.left;
        }
        int min = 1 << (leavl - 1); //最小可以有多少
        int max = ( 1 << leavl) - 1; //最大可以有多少
        int ans = 0; //存储结果
        while(min <= max){
            int middle = min + ((max - min) >> 1); 
            if(check(middle, root, leavl)){
                ans = middle;
                min = middle + 1;    //利用二分确定结果
            }
            else{
                max = middle - 1;
            }
        }
        return ans;
    }

    public boolean check(int middle, TreeNode root, int leavl){
        int jk = 1 << (leavl - 2); //抛去根节点(因为根节点是1)
        while(jk > 0){
            if((jk & middle) == 0)
                root = root.left; //为0说明在左子树上
            else
                root = root.right; //为1说明在右子树上
            jk >>= 1; //逐层进行查找
        }
        return root != null; //为空则说明不存在
    }
}

本文引自于https://leetcode.cn/problems/count-complete-tree-nodes/solutions/2456908/javapython3cer-fen-cha-zhao-wei-yun-suan-idof/