首页 > 其他 > 详细

二叉树——求一棵完全二叉树节点的个数

时间:2018-04-26 00:08:14      阅读:210      评论:0      收藏:0      [点我收藏+]

已知一棵完全二叉树, 求其节点的个数
要求: 时间复杂度低于O(N), N为这棵树的节点个数

结论:满二叉树:高度为L,结点个数  2^L  - 1个

先遍历左边界,求出完全二叉树的高度h

然后遍历树的右子树的左边界,看它到没到最后一层,

  如果到了最后一层,那么证明它的左子树是满的,高度是h-1        左子树的结点数2^(h-1) - 1  + 当前节点 + 递归求解 右子树的结点的个数

  如果没到最后一层,那么证明它的右子树是满的,高度是h-2        右子树的结点数2^(h-2) - 1  + 当前节点 + 递归求解 左子树的结点的个数

二叉树——求一棵完全二叉树节点的个数

原文:https://www.cnblogs.com/SkyeAngel/p/8947557.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!