完全二叉树的节点数

给出一个完全二叉树,求出该树的节点个数。

说明:

完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

示例:

输入:
1
/ \
2 3
/ \ /
4 5 6

输出: 6
在真实的面试中遇到过这道题?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-complete-tree-nodes
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解决该道题要充分利用完全二叉树的性质。

第一种解决方法是直接递归暴力破解

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root : return 0
        return 1 + self.countNodes(root,left) + self.countNodes(root.right)

这样写看起来简洁,但时间复杂度是O(n)
因为是完全二叉树,其效率很高,所以我们需要充分利用其的性质,二叉树的层节点数为2h1个

<pre class="EnlighterJSRAW" data-enlighter-language="null"># Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root : return 0
        left = root
        left_hight = 0
        right = root
        right_hight = 0
        while left:
            left = left.left
            left_hight += 1
        while right:
            right = right.right
            right_hight += 1
        if right_hight == left_hight:
            return pow(2, left_hight) - 1
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)
            

 

这样的方法每次只查找了左子树或右子树,时间复杂度只有O((logn)2)

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00