LeetCode 222 完全二叉树的节点个数 HERODING的LeetCode之路

48 阅读 0 评论 32 点赞

我是靠谱客的博主大方灯泡，最近开发中收集的这篇文章主要介绍LeetCode 222 完全二叉树的节点个数 HERODING的LeetCode之路，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

说明：

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

示例:

输入:
1
/
2 3
/ /
4 5 6

输出: 6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-complete-tree-nodes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：
最简单的思路还是广度优先遍历，一层层遍历直到找到空，代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root){
            return 0;
        }
        queue<TreeNode*> q;
        int sum = 0;
        q.push(root);
        while(!q.empty()){
            for(int i = 0; i < q.size(); i ++){
                TreeNode* demo = q.front();
                q.pop();
                sum ++;
                if(demo -> left){
                    q.push(demo -> left);
                }
                if(demo -> right){
                    q.push(demo -> right);
                }
            }
        }
        return sum;
    }
};

递归的方法也非常好用，很好理解，有点不讲武德啊，代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root){
            return 0;
        }
        return countNodes(root -> left) + countNodes(root -> right) + 1;
    }
};

官方还给了一种二分法的方法，有些麻烦，远远没有深度优先的递归来的简洁，代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int level = 0;
        TreeNode* node = root;
        while (node->left != nullptr) {
            level++;
            node = node->left;
        }
        int low = 1 << level, high = (1 << (level + 1)) - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (exists(root, level, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    bool exists(TreeNode* root, int level, int k) {
        int bits = 1 << (level - 1);
        TreeNode* node = root;
        while (node != nullptr && bits > 0) {
            if (!(bits & k)) {
                node = node->left;
            } else {
                node = node->right;
            }
            bits >>= 1;
        }
        return node != nullptr;
    }
};