Binary tree -- 222. Number of nodes of a complete binary tree

1 Title Description

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~ 2^h Nodes .

2 Title Example

Example 2：
Input ：root = []
Output ：0

Example 3：
Input ：root = [1]
Output ：1

3 Topic tips

The number of nodes in the tree ranges from [0, 5 * 104]
0 <= Node.val <= 5 * 104
The topic data ensures that the input tree is Perfect binary tree

4 Ideas

For any binary tree , The number of nodes can be calculated by breadth first search or depth first search , Time complexity and space complexity are both O(n), among n Is the number of nodes in a binary tree . This problem stipulates that the given tree is a complete binary tree , So we can use the characteristics of complete binary tree to calculate the number of nodes .
Specifies that the root node is located on the 0 layer , The maximum number of layers of a complete binary tree is h. According to the characteristics of complete binary tree , The leftmost node of a complete binary tree must be at the bottom , So start from the root node , Every time you visit the left child node , Until the leaf node is encountered , The leaf node is the leftmost node of the complete binary tree , The length of the path is the maximum number of layers h.

The specific way is , According to the upper and lower bounds of the number range of nodes, get the number of nodes that need to be judged at present k, If the first k Nodes exist , Then the number of nodes must be greater than or equal to k, If the first k Nodes do not exist , Then the number of nodes must be less than k, Thus, the search scope can be reduced — And a half , Until you get the number of nodes .
How to judge the second k Does a node exist ? If the first k Nodes at h layer , be k The binary representation of contains h＋1 position , The highest of these is 1, The rest of you from high to low means from the root node to the second k The path of a node ,О Represents moving to the left child node ,1 Represents moving to the right child node . By bit operation, we get the second k The path corresponding to each node , Judge whether the node corresponding to the path exists , It can be judged that k Whether a node exists .

5 My answer

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