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

题目链接 力扣https://leetcode.cn/problems/count-complete-tree-nodes/comments/这题可以通过遍历把所有的结点数出来，但是题目给的完全二叉树的性质完全没用到。

再复习一下二叉树的性质。

二叉树的性质与满二叉树和完全二叉树_KingOfMyHeart的博客-CSDN博客

其中满二叉树的结点个数计算公式为    (2^k)-1 （k>=1)

        思路就是在完全二叉树中递归地寻找满二叉树，利用公式计算出所有满二叉树的结点个数，最后相加。

        而在一颗完全二叉树的基础上判断满二叉树的方式就是，递归其左右孩子，若左右孩子深度相同，则该完全二叉树就是一颗满二叉树。

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==nullptr) return 0;
        int leftDepth=0;
        int rightDepth=0;
        TreeNode *left=root->left;
        TreeNode *right=root->right;
        while(left)//求完全二叉树左子树深度
        {
            left=left->left;
            leftDepth++;
        }
        while(right)//求完全二叉树右子树深度
        {
            right=right->right;
            rightDepth++;

        }
        if(leftDepth==rightDepth) {//相等证明该树是一颗满二叉树
            return (2 << leftDepth) - 1; 
        }
        

        return countNodes(root->left)+countNodes(root->right)+1;
        


    }
};

最后

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

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