Straight forward python O((log n) ^ 2)

  • 0

    We can start with assuming that the tree is perfect binary tree with all leaves filled out. We then check the max depth (depth of left most node rooted at the node) of the right child starting from the root. This can be used to see if our final level is filled up to the half point at the current level as we're given that all leaves are as left as possible. Thus if we see that the current level is not filled past the half point, then we subtract the right half of leaves rooted from the node on the level we're currently on. Recursively (well theoretically recursive, still can be implemented iteratively as I've done so) repeat this process until we hit the bottom.

        def countNodes(self, root):
            def max_depth(root):
                h = 0
                while root:
                    root, h = root.left, h + 1
                return h
            d = max_depth(root)
            if d < 2: return 1 if root else 0
            cnt, bottom = (1 << d) - 1, 1 << (d-2)
            while d > 1:
                _d = max_depth(root.right)
                if _d == d-1: 
                    root = root.right
                    root = root.left
                    cnt -= bottom
                d, bottom = d - 1, bottom >> 1
            return cnt

Log in to reply

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