[LeetCode 222] Count Complete Tree Nodes

作者 Shilei Tian 日期 2017-02-19
[LeetCode 222] 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.

解题思路

如果不考虑这是一个完全二叉树的,可以立即写出下面的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int countNodes(TreeNode* root) {
int count = 0;
dfs(root, count);
return count;
}

private:
void dfs(const TreeNode* root, int& count) {
if (root == nullptr) {
return;
}
++count;
dfs(root->left, count);
dfs(root->right, count);
}
};

啊,多么的简洁。时间复杂度为 O(n)。但是效果是显著的——超时!因为完全没有用到这是一个完全二叉树!

一个简单的完全二叉树如下图所示:

1
2
3
4
5
    1
/ \
2 3
/ \
4 5

我们可以发现,如果它不是一个满二叉树,那么总有一个结点,它左子树和右子树的深度是不一样的。如果一个结点左子树和右子树深度是一样的,这就说明,它是一个满二叉树。满二叉树结点的个数很容易就求得。而对于那些不是满二叉树的子树呢,我们这个时候就可以运用递归,从根节点开始将树分成两边:

1
2
3
4
5
    1
/|\
2 |3
/ \ |
4 5|

然后再递归的进行运算即可。最终的结果就是左子树的结点个数加右子树的结点个数,再加上它本身。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int depthL = 0, depthR = 0;
auto rootL = root, rootR = root;
while (rootL) {
++depthL;
rootL = rootL->left;
}
while (rootR) {
++depthR;
rootR = rootR->right;
}
if (depthR == depthL) {
return pow(2, depthR) - 1;
} else {
return 1 + countNodes(root->left) + countNodes(root->right);
}
}
};