LeetCode 222 完全二叉树的节点数

222.完全二叉树的节点数

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

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

1.1 遍历实现 DFS+BFS

DFS

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

BFS

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int count=0;
        while(!q.empty()){
            int n=q.size();
            while(n--){
                TreeNode *node=q.front();
                q.pop();
                count++;
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
        }
        return count;
    }
};

1.2 利用完全二叉树的性质实现

希望能够在小于 的时间复杂度内实现。（换句话说：能否在 的时间复杂度内实现。）重点在于最后一层，在前面层都是一个满二叉树。

从深度的角度出发计算：充分利用二叉树的性质，分别计算左右子树的深度。

• 若是左右子树的深度相等，那么左子树一定是满二叉树，再处理右子树。
• 不相等只可能是左大于右，那么右子树是满二叉树，此时在递归处理右子树。

对于完全二叉树存在如下性质：完全二叉树的子树也是完全二叉树。

针对上述性质可以推出一个特殊的求解树的深度的方式：从根节点开始不断向左查找即可得到完全二叉树的深度。

class Solution {
public:
    int getDepth(TreeNode *root){
        int depth=0;
        while(root){
            depth++;
            root=root->left;
        }
        return depth;
    }
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        int d_left=getDepth(root->left);
        int d_right=getDepth(root->right);
        if(d_left==d_right){ // 当前左子树是满的
            return (1<<d_left)+countNodes(root->right);
        }else{ // 右子树是满的
            return countNodes(root->left)+(1<<d_right);
        }
    }
};