222.完全二叉树的结点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例 1：

输入：root = [1,2,3,4,5,6]
输出：6

思路：结合满二叉树与普通二叉树计算结点个数的逻辑

时间复杂度为O(logN*ogN)，因为完全二叉树的两棵子树，至少有一颗是满二叉树。

 时间复杂度=递归的次数*每次递归的时间复杂度

递归的次数为二叉树的深度logN，因为完全二叉树的两棵子树，至少有一颗是满二叉树(看代码)

每次递归的时间复杂度为logN，因为每次递归时都是采取满二叉树的计算逻辑(求得子树深度，再利用公式计算)

class Solution {
public:
    int count=0;
    int countNodes(TreeNode* root) {
        int leftHigh=0;
        int rightHigh=0;
        TreeNode* l=root;
        TreeNode* r=root;
        while(l)//左子树高度
        {
            leftHigh++; 
            l=l->left;
        }
        while(r)//右子树高度
        {
            rightHigh++;
            r=r->right;
        }
        if(leftHigh==rightHigh)//左右子树高度相等就是满二叉树
        {
            return pow(2,leftHigh)-1;
        }
        else//不相等就是完全二叉树，采用普通二叉树的逻辑计算
        {
            int leftNode=countNodes(root->left);
            int rightNode=countNodes(root->right);
            return 1+leftNode+rightNode;
;
        }
    }
};

最后

以上就是隐形麦片为你收集整理的222.完全二叉树的结点个数的全部内容，希望文章能够帮你解决222.完全二叉树的结点个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。