求完全二叉树的节点个数。
完全二叉树要么是满二叉树(满二叉树：节点个数为2^n - 1个)要么最后一层的节点都是从左往右都是齐全的。
用递归的方法来解决问题：
1
2
3
4
5
6
7
8
9
| public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
|
主代码：
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
| public static int nodeNum(Node head) {
if (head == null) {
return 0;
}
return bs(head, 1, mostLeftLevel(head, 1));
}
public static int bs(Node node, int l, int h) {
if (l == h) {
return 1;
}
if (mostLeftLevel(node.right, l + 1) == h) {
return (1 << (h - l)) + bs(node.right, l + 1, h);
} else {
return (1 << (h - l - 1)) + bs(node.left, l + 1, h);
}
}
public static int mostLeftLevel(Node node, int level) {
while (node != null) {
level++;
node = node.left;
}
return level - 1;
}
|