求完全二叉树节点的个数时间复杂度不能大于O(n)_完全二叉树的节点个数时间复杂度

作者：Guff_9hys | 2024-07-18 09:05:02

踩

完全二叉树的节点个数时间复杂度

首先知道一个公式：

如果一棵二叉树为满二叉树，那么该满二叉树的节点个数为(2^h)-1，其中h为该满二叉树的高度。

我们利用这一个公式来实现求完全二叉树的节点的个数，并且时间复杂度不大于O(n)。

通过寻找整棵二叉树的满二叉子树，找到后直接运用公式求该满二叉子树的节点个数。这样就省去了遍历二叉树的时间，使算法的时间复杂度降低。

我们以下图为例讲：

图一

图二

1：先求出整棵二叉树的层数h，上图一中h等于4。

2：然后求出这个二叉树的右子树最左的节点所在的层数

3：如果右子树最左的节点所在的层数等于整棵二叉树的层数，上图一，那么这个二叉树的左子树就是一个满二叉树

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Guff_9hys/article/detail/844664

求完全二叉树节点的个数 时间复杂度不能大于O(n)_完全二叉树的节点个数 时间复杂度