LeetCode 222 [Count Complete Tree Nodes]

题目链接

题目描述

  • 给定一棵完全二叉树,要求计算它的总结点数。完全二叉树指的是除了最后一层之外,其他每一层都是完整的,最后一层可能不是完整的,但是这一层的结点全部聚集在左侧,因此完全二叉树的结点数落在(1,2^h)这个区间内。

解题思路

  • 一开始我使用最简单的方式来处理,完全二叉树是特殊的二叉树,只要把它的结点全部遍历一次就可以了。这种方法可以得到结果,但是时间复杂度为O(n),直接超时了
  • 接着我改进了计算方式,从最右侧开始遍历,当发现最后一层某个位置有结点的时候就停止。这种方法在平均情况下只需要遍历一半的结点,但是时间复杂度还是O(n),还是超时
  • 时间复杂度为O(n)行不通,只能考虑O(log n)的算法,而O(log n)的时间复杂度一般对应着二分法。对于这个题目,可以通过二分法查找最后一层的最后一个结点的位置,进而计算出总结点数,具体的算法如下:
    1. 首先计算树的高度,由根结点一直往左偏移,计算偏移次数即可,这一步的时间复杂度为O(log n)
    2. 除了树为空或者仅有根结点的情况,完全二叉树的倒数第二层肯定是完整的,因此可以通过倒数第二层的结点来判断最后一层的结点的分布情况
    3. 从根结点开始处理,以当前结点为中间线,将以当前结点为根的二叉树分成两部分,取倒数第二层中,左半部分最靠近中间线的结点,即之前描述的二分的方式。这个处于“二分位置偏左”的结点,称之为“二分结点”,必然是当前结点的左子树(不考虑原树最后一层)的最右边的结点
    4. 如果“二分结点”有右子结点,说明上述的左半部分是完整的,继续考虑右半部分,将当前结点向它的右结点偏移
    5. 如果“二分结点”没有右子结点,说明上述的左半部分不是完整的,右半部分最后一层的结点全部缺失,记录对应的缺失结点数之后,将当前结点向它的左结点偏移
    6. 对新的当前结点进行处理,直到当前结点位于倒数第二层,这种情况下以当前结点为根的树(不考虑原树最后一层)仅有一个结点,无法拆分为左右两部分,因此直接根据它的左右子结点是否为空,对应记录缺失的结点数即可
    7. 倒数第二层处理完之后,处理流程结束,计算相同高度的满二叉树的结点数,用它减去缺失的结点数,即为所求的完全二叉树的结点数

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#include <math>
class Solution {
public:
int countNodes(TreeNode* root) {
// 计算树的高度
int height = 0;
TreeNode* tmp = root;
while (tmp) {
height++;
tmp = tmp->left;
}
// 记录缺少的结点数
int numRightEmpty = 0;
TreeNode* node = root;
TreeNode* curNode;
int level = 1;
int curLevel;
// 从根结点开始遍历,直到当前结点为空,或者已遍历到最后一层
while (node && level < height) {
// 如果当前结点位于倒数第二层,则处理完它的子结点的情况之后即可结束
if (level == height - 1) {
numRightEmpty += node->right ? 0 : node->left ? 1 : 2;
break;
}
// 以当前结点位置为中间线,查找倒数第二层里面,中间线偏左的最后一个元素
// 查找方法为当前结点向左下方偏移,再一直向右下方偏移,直到倒数第二层为止
curNode = node->left;
curLevel = level + 1;
while (curLevel < height - 1) {
curNode = curNode->right;
curLevel++;
}
// 如果中间线偏左的最后一个元素有右子结点,则需要将当前结点重置为它的右子结点
// 如果中间线偏左的最后一个元素没有右子结点,那么说明当前结点缺少了右半边的叶子结点,对应处理之后,将当前结点重置为它的左子结点
if (curNode->right) {
node = node->right;
} else {
numRightEmpty += (int)pow(2.0, (double)(height - level - 1));
node = node->left;
}
level++;
}
// 总的结点数为(2^h - 1 - 缺少的结点数)
return (int)pow(2.0, (double)(height)) - 1 - numRightEmpty;
}
};