题目描述：

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

题目大意：

给定一棵完全二叉树，计算其中节点的个数。

维基百科关于完全二叉树的定义如下：

在一棵完全二叉树的每一层，除最后一层外，其余各层都是填满的，并且最后一层的节点尽可能的靠左排列。最后一层（第h层）包含的节点个数介于[1, 2^h]区间之内。

解题思路：

解法I：二分枚举

高度为h的完全二叉树，其节点个数等于高度为h-1的满二叉树的节点个数 + 最后一层的节点个数。

因此，只需要二分枚举第h层的节点个数即可。

将第h层的节点从0至2^h - 1依次编号（根节点的层数记为0）

若用0表示左孩子，1表示右孩子，则这些编号的二进制形式是从根节点出发到叶子节点的“路径”。

例如高度为2，包含6个节点的完全二叉树：

Lv0        1 
         /    \
Lv1     2      3
       /  \   /  \
Lv2   4   5  6   -

No.   00  01 10

从1号节点（根节点）出发，到第5号节点的路径为01（左右），同时该节点为第2层的第2个节点。

C++代码：

/**
 * 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) {
        int depth = 0;
        TreeNode* node = root;
        while (node) {
            depth++;
            node = node->left;
        }
        if (depth == 0) {
            return 0;
        }
        int left = 0, right = (1 << (depth - 1)) - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (getNode(root, mid, depth - 1)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return (1 << (depth - 1)) + right;
    }
    TreeNode* getNode(TreeNode* root, int path, int depth) {
        while (depth-- && root) {
            if (path & (1 << depth)) {
                root = root->right;
            } else {
                root = root->left;
            }
        }
        return root;
    }
};

解法II：递归

参考LeetCode Discuss：https://leetcode.com/discuss/38899/easy-short-c-recursive-solution

如果当前子树的“极左节点”（从根节点出发一路向左）与“极右节点”（从根节点出发一路向右）的高度h相同，则当前子树为满二叉树，返回2^h - 1

否则，递归计算左子树与右子树的节点个数。

C++代码：

/**
 * 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;
        int hl = 0, hr = 0;
        TreeNode *l = root, *r = root;
        while(l) {hl++; l = l->left;}
        while(r) {hr++; r = r->right;}
        if (hl == hr) return pow(2, hl) - 1;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

 

本文链接：http://bookshadow.com/weblog/2015/06/06/leetcode-count-complete-tree-nodes/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码