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

前言

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

参考题解：完全二叉树的节点个数-代码随想录

提交代码

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

方法一：深度遍历或者广度遍历的过程中，记录节点个数。

方法二：使用递归，充分利用完全二叉树的性质。如果当前树是完全二叉树，树节点个数为

2^(h-1)-1

。如果当前树不是完全二叉树，树节点个数为

1+左子树节点个数+右子树节点个数

。时间复杂度最差为 O ( l o g n ∗ l o g n ) O(logn*logn) O(logn∗logn)，最好为 O ( l o g n ) O(logn) O(logn)

class Solution {
public:
    int countNodes(TreeNode* root) {
        // 如果当前树是完全二叉树。树节点个数：2^(h-1)-1
        // 如果当前树不是完全二叉树。树节点个数：1+左子树节点个数+右子树节点个数
        if(root == nullptr) 
            return 0;
        
        int leftDepth = 0; // 左子树高度
        int rightDepth = 0; // 右子树高度
        TreeNode* leftNode = root->left;
        TreeNode* rightNode = root->right;

        while(leftNode != nullptr){
            leftDepth++;
            leftNode = leftNode->left;
        }

        while(rightNode != nullptr){
            rightDepth++;
            rightNode = rightNode->right;
        }

        if(leftDepth == rightDepth){ //以root为根节点的树为满二叉树
            return (2<<(leftDepth+1-1))-1;
        }else{
            return 1 + countNodes(root->left) + countNodes(root->right);
        }

    }
};