文章目录
222. 完全二叉树的节点个数
解题思路
代码
222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-complete-tree-nodes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
完全二叉树的高度怎么求?一直往左看，看最深到第几层就是完全二叉树的高度
首先数一下一共有几层，然后找右数上的最左节点如果没有达到最大深度5层，现在只有4层说明
右树是满的，高度是3
因为我们永远有总层数,如果总层数10层,
如果当前节点在第5层,如果发现右树上的最左节点没到第10层,到第9层
说明右树是满的,高度是4
右树节点个数为24
如果总层数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;
}
}
