[LeetCode]Count Complete Tree Nodes

题目描述:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

评论
  1. King King 发布于 2015年6月9日 14:09 #

    第一种方法如果 h > 32 还能得出正确结果吗?

  2. 在线疯狂 在线疯狂 发布于 2015年6月9日 15:38 #

    对于Python来说可以,Python的long类型可以支持非常大的数

  3. Roman终将成为威尼斯人 Roman终将成为威尼斯人 发布于 2015年6月11日 08:52 #

    第二种方法leetcode不能accept,Last executed input: Special Judge: very large tree

  4. 在线疯狂 在线疯狂 发布于 2015年6月11日 09:29 #

    刚才试了一下,可以通过,你指的是C++代码吗?

  5. Roman终将成为威尼斯人 Roman终将成为威尼斯人 发布于 2015年6月18日 05:25 #

    额,我没说清楚。我用的java,最慢的~

  6. xiaolittle xiaolittle 发布于 2015年7月18日 10:47 #

    为什么left = (1 << (dep - 2)) - 1就不行呢?感觉只需要算最后一层就好了啊?

张贴您的评论