leetcode-222题:count complete tree nodes

题目：Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

思路：如果知道一个子树是完全二叉树，并且其深度为h，那么这棵子树所包含的节点个数便为2^h-1。否则便需递归求其左右子树的节点个数。

代码：

def getHightRight(self, root):
    if root == None:
        return 0
    high = 0
    while root != None:
        high += 1
        root = root.right
    return high

def getHightLeft(self, root):
    if root == None:
        return 0
    high = 0
    while root != None:
        high += 1
        root = root.left
    return high

def countNodes(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    if root == None:
        return 0
    l_high = self.getHightLeft(root.left)
    r_high = self.getHightRight(root.right)
    if l_high == r_high:
        return 2**(l_high+1)-1
    else:
        return　self.countNodes(root.left)+self.countNodes(root.right)+1

leetcode-222题:count complete tree nodes

近期文章

近期评论

标签

热门

文章归档

分类目录

功能