leetcode222. 完全二叉树的节点个数

bfs

class Solution {
public:
    int countNodes(TreeNode* root) {
        int num=0;
        if(root==nullptr)return num;
        queue<TreeNode*>q;
         q.push(root);
         while(q.size()){
             auto t=q.front();
             q.pop();
             num++;
             if(t->left)q.push(t->left);
             if(t->right)q.push(t->right);
         }
         return num;
    }
};

dfs

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

优化

class Solution {
public:
    //获得高度
    int countLevels(TreeNode*root){
        int levels=0;
        while(root){
            levels++;
            root=root->left;
        }
        return levels;
    }
    int countNodes(TreeNode* root) {
        if(!root)return 0;
        int left=countLevels(root->left);
        int right=countLevels(root->right);
        if(left==right){
            return countNodes(root->right)+(1<<left);//左右子树深度相同说明左子树是满的，只需计算右子树
        }else {
            return countNodes(root->left)+(1<<right);//左>右子树深度说明右子树是满的，只需计算左子树
        }
    }
};