Skip to content

222 count complete tree nodes

222. Count Complete Tree Nodes

题目: https://leetcode.com/problems/count-complete-tree-nodes/

难度: Medium

思路:

思路一: 超时,跟一般的树一样,递归的来数nodes数

class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0
        if root.left == None and root.right == None:
            return 1
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

思路二:既然说了是 complete binary tree,那么必然有特性可用,complete binary tree的特性是除了最后一层,之前的就是perfect tree.

所以寻找左子树的最左边的高度和右子树的最右边的node高度,如果相同就是perfect tree,高度2^h - 1, 否则递归的来看左子树和右子树


class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0

        p, q = root,root

        leftHeight = 0
        rightHeight = 0

        while p:
            p = p.left
            leftHeight += 1

        while q:
            q = q.right
            rightHeight += 1

        if leftHeight == rightHeight:
            return (int)(math.pow(2,leftHeight) - 1)
        else:
            return 1 + self.countNodes(root.left) + self.countNodes(root.right)


回到顶部