Python Clean and Fast Solution: O(h^2)


  • 1
    D

    Inspiration from @yuleleegerlee

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def countNodes(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            def query_depth(node):
                h = 0
                while node:
                    h += 1
                    node = node.right
                return h
                
            d = query_depth(root)
            def count(node, depth):
                if not node: return 0
                if query_depth(node.left) == depth-1:
                    return 2**(depth - 2) + count(node.right, depth - 1)
                return count(node.left, depth - 1)
                
            return count(root, d+1) + 2**d-1

Log in to reply
 

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