Python solution with detailed explanation

  • 0


    Count Complete Tree Nodes


    1. We need to use the idea of complete tree here.
    2. Find the left depth (ld) and right depth (rd).
    3. Only two cases are possible: ld == rd or ld > rd. rd can never be greater than ld because of the manner in which nodes are packed in the last level.
    4. When ld == rd, then we are sure that left sub-tree is full. The right may or may not be full, but has same depth. Sketch a diagram to get the intuition.
    5. When ld > rd, then we know that right subtree is full. Sketch a diagram to get the intuition.
    6. Complexity: O(lgN * lgN) - There are lg(N) steps and in each step we do lg(N) work of finding the depth.
    class Solution(object):
        def depth(self, root):
            if not root:
                return 0
            return 1 + self.depth(root.left)
        def countNodes(self, root):
            :type root: TreeNode
            :rtype: int
            if root == None:
                return 0
            l_d = self.depth(root.left)
            r_d = self.depth(root.right)
            if l_d > r_d:
                return (2**r_d - 1) + self.countNodes(root.left) + 1
                return (2**l_d - 1) + self.countNodes(root.right) + 1

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.