Topic describes

Given the root node of a complete binary tree, find the number of nodes in the tree.

A complete binary tree is defined as follows: In a complete binary tree, the number of nodes in each layer reaches the maximum except that the lowest node may not be filled, and the nodes in the lowest layer are concentrated in the leftmost positions of the layer. If the lowest layer is layer H, this layer contains 1 to 2h nodes.

Input: root = [1,2,3,4,5,6] output: 6Copy the code

Thought analysis

First of all, the simplest way we can think of is to walk through the whole tree, so that we know how many nodes there are in the whole tree, which is order n time.

But we need to know that this is a perfect binary tree, and we can do this based on the properties of perfect binary trees.

In the first case, as shown in the figure above, the right subtree is a full binary tree, and its node number can be obtained by the formulacount = 2 ^ (hight - 1), and then we recursively traverse the left subtree to get all the nodes.

In the second case, as shown in the figure, the left subtree is a full binary tree, and its node number can be obtained by the formulacount = 2 ^ (hight - 1), and then we recursively traverse the right subtree to get all the nodes.

AC code

The first conventional solution:

 public int count(TreeNode node){
     return node == null ? 0 : count(node.left) + count(node.right) + 1;
 }
Copy the code

The second solution using the complete binary tree property:

public int countNodes(TreeNode root) { 
    if(root == null) return 0;

    // Get the height of the left subtree
    int leftHight = treeHight(root.left);
    if(leftHight == 0) {return 1;
    }

    // Get the height of the right subtree
    int rightHight = treeHight(root.right);

    // If the height of the left subtree is equal to the height of the right subtree, it indicates that the left subtree is a full binary tree
    if(leftHight == rightHight){
        return (1 << leftHight) + count(root.right);
    } else {
        // If the height of the left subtree is greater than the height of the right subtree, the right subtree is a full binary tree
        return (1<< rightHight) + count(root.left); }}public int treeHight(TreeNode root){
    return root == null ? 0 : treeHight(root.left) + 1;
}

public int count(TreeNode node){
    return node == null ? 0 : count(node.left) + count(node.right) + 1;
}
Copy the code

conclusion

This problem is mainly to test whether we understand the properties of a complete binary tree, when we get the problem, the first feeling is to directly recurse through all the nodes, but when we see a complete binary tree, we need to think about whether we can use its properties, rather than simply solve the problem.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign