222 Count Complete Tree Nodes

222. Count Complete Tree Nodes

1. Question

Given acompletebinary tree, count the number of nodes.
Definition of a complete binary tree fromWikipedia: 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 2hnodes inclusive at the last level h.

2. Implementation

(1) Method 1
思路: 对于每个node,找出最左边和最右边的高度,如果这两个高度相同,说明这个树是完美二叉树,其node的数目等于 2^height - 1。如果这两个高度不同,递归地检测它的左子树和右子树是否完美二叉树,是的话就可以直接用公式计算, node数目等于它这个node加上左子树的node和右子树的node
1
class Solution {
2
public int countNodes(TreeNode root) {
3
if (root == null) {
4
return 0;
5
}
6
7
int leftMostHeight = getHeight(root, true);
8
int rightMostHeight = getHeight(root, false);
9
10
if (leftMostHeight == rightMostHeight) {
11
return (1 << leftMostHeight) - 1;
12
}
13
14
return 1 + countNodes(root.left) + countNodes(root.right);
15
}
16
17
public int getHeight(TreeNode node, boolean isLeft) {
18
int height = 0;
19
20
while (node != null) {
21
if (isLeft) {
22
node = node.left;
23
}
24
else {
25
node = node.right;
26
}
27
++height;
28
}
29
return height;
30
}
31
}
Copied!
(2) Method 2 二分法
思路:根据Complete tree的leaf node as far left as possible的特点,对一个节点的左子树和右子树,我们分别找出最左的深度。如两边最左深度相同,说明左子树是完美二叉树,可以直接用公式计算node个数,否则右边子树的高度肯定小于左边子树,而且右边子树根据complete的特点也必然是完美二叉树,用公式计算其node个个数。这样就可以达到二分的效果
1
class Solution {
2
public int countNodes(TreeNode root) {
3
if (root == null) {
4
return 0;
5
}
6
7
int count = 1;
8
9
int leftHeight = getLeftMostHeight(root.left);
10
int rightHeight = getLeftMostHeight(root.right);
11
12
if (leftHeight == rightHeight) {
13
count += (1 << leftHeight) - 1;
14
count += countNodes(root.right);
15
}
16
else {
17
count += (1 << rightHeight) - 1;
18
count += countNodes(root.left);
19
}
20
return count;
21
}
22
23
public int getLeftMostHeight(TreeNode node) {
24
int height = 0;
25
while (node != null) {
26
node = node.left;
27
++height;
28
}
29
return height;
30
}
31
}
Copied!

3. Time & Space Complexity

Method 1: 时间复杂度 O(h^2), 解析: 最坏的情况是每个子树都不是完美二叉树,所以对于每个node,都要花2h的时间去找出它的左子树和右子树的高度,总的时间为 2h + 2(h-1) + 2(h-2) +. ... + 2 => O(h^2), 空间复杂度O(h)
Method 2: 时间复杂度: O(h^2), 空间复杂度O(h)

4. References