222. Number of nodes of complete binary tree

---

222. The number of nodes in a complete binary tree

Here's a tree for you Perfect binary tree The root node root , Find out the number of nodes of the tree .

Perfect binary tree Is defined as follows ： In a complete binary tree , Except that the lowest node may not be full , The number of nodes in each layer reaches the maximum , And the nodes of the lowest layer are concentrated in the leftmost positions of the layer . If the bottom layer is No h layer , Then the layer contains 1~ 2h Nodes .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/count-complete-tree-nodes
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking

How to find the height of a complete binary tree ? Keep looking to the left , The deepest layer is the height of a complete binary tree
First, count the total number of floors , Then find the leftmost node on the right number if it does not reach the maximum depth 5 layer , Now only 4 Layer description
The right tree is full , Height is 3

Because we always have a total number of floors , If the total number of floors 10 layer ,
If the current node is at 5 layer , If you find that the leftmost node on the right tree does not reach the 10 layer , To the first 9 layer
It shows that the right tree is full , Height is 4
The number of nodes in the right tree is 2⁴

If the total number of floors 10 layer , The leftmost node on the right tree arrives at 10 layer , It shows that the left tree is full , Height is 5

Always find the leftmost tree on the right of the node
If it reaches the last floor , The direct formula on the left is solved
If it doesn't reach the last floor , Find the formula on the right , Then go left recursion .
Always look at the leftmost tree on the right to decide whether you go left or right

Code

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;
    }
        
}