---

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-complete-tree-nodes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

完全二叉树的高度怎么求?一直往左看，看最深到第几层就是完全二叉树的高度
首先数一下一共有几层，然后找右数上的最左节点如果没有达到最大深度5层，现在只有4层说明
右树是满的，高度是3

因为我们永远有总层数,如果总层数10层,
如果当前节点在第5层,如果发现右树上的最左节点没到第10层,到第9层
说明右树是满的,高度是4
右树节点个数为2⁴

如果总层数10层，右树上的最左节点到了第10层，说明左树是满的,高度是5

永远在找头节点右树上的最左
它如果到了最后一层,左边直接公式求出来了
它如果没到最后一层， 右边一个公式求出来,之后走左边递归。
永远都看右树最左决定你走左还是走右

代码

class Solution {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        return bs(root,1,mostLestLevel(root,1));
    }
    public int bs(TreeNode root,int level,int h){
        if(level==h){
            return 1;
        }
        if(mostLestLevel(root.right,level+1)==h){
            return (1<<(h-level))+bs(root.right,level+1,h);
        }else{
            return (1<<(h-level-1))+bs(root.left,level+1,h);
        }
    }
    public int mostLestLevel(TreeNode node,int level){
        while(node!=null){
            level++;
            node=node.left;
        }
        return level-1;
    }
        
}
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