Not sure if this is a new O(h^2) solution, but I think it is easy to come up and understand.


  • 0
    X

    Idea is simple:
    Firstly, I get the max depth of the tree by going to the left most node (d);
    Then, I binary search the right-most node that exist in the d-th level (check function returns whether there is the m-th node in the d-th level).

    class Solution(object):
    def check(self, root, m, d):
        if root == None:
            return False
        elif d == 0:
            if root.left == None and root.right == None:
                return True
        if m > 2**(d - 1):
            return self.check(root.right, m - 2**(d - 1), d - 1)
        else:
            return self.check(root.left, m, d - 1)
    def countNodes(self, root):
        n, d = root, -1
        while n != None:
            d += 1
            n = n.left
        l, r = 1, 2**d
        while l < r:
            m = (l + r + 1)/2
            if self.check(root, m, d):
                l = m
            else:
                r = m - 1
        return l + 2**d - 1 if d >= 0 else 0

Log in to reply
 

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