腾讯云开发者社区-腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

mathor

专栏作者

447

文章

591395

阅读量

50

订阅数

判断一棵树是否为完全二叉树

例如下图所示的情况，当遍历到红色节点后，由于其只有左孩子，没有右孩子，因此实际上认为当前开启了一个状态，这个状态的开启，使得接下来的所有节点必须只能是叶子节点，如果不是，则该二叉树不是完全二叉树。例如，接下来访问到绿色节点，发现该节点不是叶子节点，因此直接返回false

2020-05-26

5290

LeetCode222. 完全二叉树的节点个数

常规思路，遍历整棵树，时间复杂度O(N)，但是有一种时间复杂度小于O(N)的做法首先遍历头结点右子树的最左边界，如果最左边界不为空，说明头结点的左子树是满二叉树，利用满二叉树的性质，结点个数就为2^h^-1，再加上头结点，所以结果就是2^h^，这个时间复杂度是O(logN)的，然后再递归遍历右子树求出有多少结点即可如果最左边界为空，说明头结点的右子树是一棵高度为h-1的满二叉树，那么右子树加上头结点的总结点个数就为2^h-1^，然后再递归遍历头节点的左子树即可

2018-08-17

9200

编程算法二叉树

Morris算法遍历一棵二叉树，时间复杂度O(n)，但是空间复杂度却只用神奇的O(1)，下面说一下Morris遍历的流程，首先规定来到的当前结点即为cur

2018-08-17

3550

没有更多了

社区活动

腾讯技术创作狂欢月

“码”上创作 21 天，分 10000 元奖品池！

Python精品学习库

代码在线跑，知识轻松学

博客搬家 | 分享价值百万资源包

自行/邀约他人一键搬运博客，速成社区影响力并领取好礼

技术创作特训营·精选知识专栏

往期视频·千货材料·成员作品最新动态