Python solution with detailed explanation


  • 0
    G

    Solution

    Count Complete Tree Nodes https://leetcode.com/problems/count-complete-tree-nodes/?tab=Description

    Algorithm

    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.
    7. https://goo.gl/photos/eQJej6mGcToiRwGY6
    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
            else:
                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.