Leetcode解题: Count Complete Tree Nodes (222)

发表于 | 分类于

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 2h nodes inclusive at the last level h.

解法1： O(logN * logN）

这题参考了Discussion的解法， 用遍历的方法的话，复杂度是O（N）， 但并没有用到complete BT的性质，显然最后的结果是TLE。
在巧妙的解法里，运用complete tree的一个性质是： 如果从一个root出发，最左面和最右面的高度一致的话，那么一定是一个complete tree，他的节点个数是pow(2, k) - 1, k是高度。
这个的运算的复杂度是O(logN).
如果高度不一致的话，那么可以对左右各做一次操作， 也就是一个递归操作。
复杂度分析
T（n) = T(n/2) + clogN = T（n/4) + clogN + c1(logN - 1) = … = T(1) + c[logN + logN - 1 + logN - 2 + … + 1] => O(logN logN)

logN*logN是比N好很多的，比如1024， logN = 10， N = 1024， 显然这个解法的复杂度好很多。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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 left = 0, right = 0;
        TreeNode* toleft = root, *toright = root;
        while (toleft) {++left; toleft = toleft->left;}
        while (toright) {++right; toright = toright->right;}
        if (left == right) return (1 << left) - 1;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

Java

1