AC Python iterative solution O(h^2) time O(1) space 148ms


  • 2
    def countNodes(self, root):
        if not root:
            return 0
    
        def leftDepth(node):
            d = 0
            while node:
                d += 1
                node = node.left
            return d
    
        ans = 1
        for i in xrange(leftDepth(root) - 1, 0, -1):
            ans <<= 1
            if leftDepth(root.right) == i:
                ans |= 1
                root = root.right
            else:
                root = root.left
        return ans
    
    
    # 18 / 18 test cases passed.
    # Status: Accepted
    # Runtime: 148 ms
    # 100%
    

    The idea is find the last node in the deepest level and convert the path from root to this node into a binary number. For example

         1
        / \
       2   3
      /\
     4  5
    

    The last node is 5 and it's path is (root, left, right) = 0b101 = 5.


Log in to reply
 

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