Leetcode Count Complete Tree Nodes problem solution

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        frontier = [root]
        level = 0
        last = None
        while frontier:
            new = []
            level += 1
            for node in frontier:
                if node.left == None or node.right == None:
                    # last is the last level with full nodes
                    last = level
                new.append(node.left)
                new.append(node.right)
            
            if last == None:
                frontier = new
            else:
                temp = 0
                for i in range(last):
                    temp += 2**i
                return len([elt for elt in new if elt != None]) + temp

int count = 0;
    public int countNodes(TreeNode root) {
        helper(root);
        return count;
    }

    private void helper(TreeNode node){
        if (node == null) return;
        count++;
        helper(node.left);
        helper(node.right);
    }

class Solution {
public:
    int countNodes(TreeNode* root) {
        int res = 0;
        int depth = 0;
        int tmp = 0;
        int cnt = 0;
        bool flag = true;
        bool virgin = true;
        countNodesDFS(root, depth, tmp, cnt, flag, virgin);
        int plus = 1;
        for(int i = 0; i < depth; i++){
            res += plus;
            plus *= 2;
        }
        res = res - (plus / 2) + (cnt / 2);
        return res;
    }
    
    void countNodesDFS(TreeNode* cur, int& depth, int &tmp, int &cnt, bool &flag, bool &virgin){
        if(flag == false)
            return;
        if(cur == NULL){
            if(virgin == true){
                depth = tmp;
                virgin = false;
            }
            if(tmp == depth)
                cnt++;
            else
                flag = false;
            return;
        }
        tmp += 1;
        countNodesDFS(cur->left, depth, tmp, cnt, flag, virgin);
        countNodesDFS(cur->right, depth, tmp, cnt, flag, virgin);
        tmp -= 1;
    }
    
};

void count_nodes(struct TreeNode* root, int* size){
    if(root==NULL){
        *size=0;
        return;
    }
    int l_subtree_size, r_subtree_size;  
    count_nodes(root->left, &l_subtree_size);
    count_nodes(root->right, &r_subtree_size);
    *size=l_subtree_size+r_subtree_size+1;
}

int countNodes(struct TreeNode* root){
    int size=0;
    count_nodes(root, &size);
    return size;
}