Welcome to you,  Daily brush series

The number of nodes in a complete binary tree

recursive

iteration

Optimize practices

The number of nodes in a complete binary tree

Let's use ordinary binary tree to solve this problem . Find the number of nodes of an ordinary binary tree , Nothing more than recursion or iteration .

Recursion is similar to what we said earlier The maximum depth of a binary tree similar , Iteration is the same as what we said earlier The maximum depth of a binary tree The code is very similar , Just change a little .

recursive

According to the recursive trilogy .

1. Determine the parameters and return values of recursive functions : The parameter is the root node of the incoming tree , Returns the number of nodes in the binary tree with this node as the root node , So the return value is int type .

 int _countNodes(TreeNode* root)

2. Determine the single-layer loop logic :  First find the number of nodes in its left subtree , Then find the number of nodes of the right subtree , Finally, take the sum and add one （ Add 1 Because the current intermediate node is included ） This is the number of nodes whose current node is the root node .

int leftnum=_countNodes(root->left);
int rightnum=_countNodes(root->right);
int treenum=leftnum+rightnum+1;
return treenum;

3. Determine the closing conditions :

if(root==nullptr)
{
  return 0;
}

Code :

class Solution {
public:
    int countNodes(TreeNode* root) {
     if(root==nullptr)
     {
         return 0;
     }
     int left=countNodes(root->left);
     int right=countNodes(root->right);
     return left+right+1;
    }
};

iteration

The template of sequence traversal mentioned earlier , You can go and have a look , Here I'll go straight to the code

Code :

class Solution {
public:
    int countNodes(TreeNode* root) {
     if(root==nullptr)
     {
         return 0;
     }
     queue<TreeNode*> q;
     q.push(root);
     int result=0;
     while(!q.empty())
     {
         int size=q.size();
         for(int i=0;i<size;i++)
         {
             TreeNode* node=q.front();
             q.pop();
             result++;
             if(node->left) q.push(node->left);
             if(node->right) q.push(node->right);
         }
     }
     return result;
    }
};

Let's take a look at the time complexity and space complexity of the above code :

recursive :  

• Time complexity ：O(n)
• Spatial complexity ：O(log n)

iteration : 

• Time complexity ：O(n)
• Spatial complexity ：O(n)

Can we use the characteristics of complete binary tree to optimize the time complexity ？

Optimize practices

Completely Binary trees are more special than ordinary binary trees , But it's not as special as a full binary tree , Calculate its total number of nodes , It can be said to be a combined version of ordinary binary tree and full , Look at the code first ：

If it's a Ordinary Binary tree , Obviously, you just have to traverse one side down like this , Time complexity O(N)：

int countNodes(TreeNode* root) {
    return 1+countNodes(root->left)+countNode(root->right);
    }

If it's a tree full Binary tree , The total number of nodes is exponentially related to the height of the tree ：

int countNodes(TreeNode* root) {
    int h = 0;
    //  Calculate the height of the tree 
    while (root != null) {
        root = root.left;
        h++;
    }
    //  The total number of nodes is  2^h - 1
    return (int)Math.pow(2, h) - 1;
}

Code :

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==nullptr)
        {
            return 0;
        }
       TreeNode* l=root;
       TreeNode* r=root;
       // Record the height of the left and right subtrees 
       int h1=0,h2=0;
       while(l!=nullptr)
       {
           l=l->left;
           h1++;
       }
       while(r!=nullptr)
       {
           r=r->right;
           h2++;
       }
       // If the height of the left and right subtrees is the same , Is a full binary tree 
       if(h1==h2)
       {
           return (int)pow(2, h1) - 1;
       }
       // If the height is different, it is calculated according to the ordinary binary tree 
       return countNodes(root->left)+countNodes(root->right)+1;
    }
};

• Time complexity ：O(log n × log n)
• Spatial complexity ：O(log n)

So ,「 Perfect binary tree 」 There are still reasons for this concept , It's not only suitable for arrays to implement binary heaps , And even the seemingly simple operation of calculating the total number of nodes has efficient algorithm implementation .