222. Count Complete Tree Nodes

1. 题解

很明显，O(n)是肯定过不了的，我们所用的方法如下

  • 往左遍历得到高度h1， 往右遍历得到高度h2
  • 如果 h1 == h2, 说明是满2叉树， 直接计算
  • 如果 h1 != h2, 则 递归为cal(root->left) + cal(root->right) + 1

2. 复杂服分析（重点）

首先，因为每次递归就会把问题对象的高度减1，所以最多把这个问题递归O(h)次， 而每次计算又最多需要O(h)来计算是否是满二叉树。所以本解法的复杂度是O(h^2).

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容