这题是利用完全二叉树的性质计算节点数目。那么是通过比较左右子树的最左结点的高度来看那边是满的，然后递归计算。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 |
//使用getLeftChildNode(TreeNode)获得左儿子结点//使用getRightChildNode(TreeNode)获得右儿子结点//使用isNullNode(TreeNode)判断结点是否为空int
get_left_height(TreeNode root) { if
(isNullNode(root)) { return
0; } else
{ return
get_left_height(getLeftChildNode(root)) + 1; }}int
count_complete_binary_tree_nodes(TreeNode root) { if
(isNullNode(root)) return
0; TreeNode leftNode = getLeftChildNode(root); TreeNode rightNode = getRightChildNode(root); int
lheight = get_left_height(leftNode); int
rheight = get_left_height(rightNode); if
(lheight == rheight) { return
(1 << lheight) + count_complete_binary_tree_nodes(rightNode); } else
{ return
(1 << rheight) + count_complete_binary_tree_nodes(leftNode); }} |
原文：http://www.cnblogs.com/lautsie/p/3521786.html