Must be shortest solution with O(n) time and O(log n) space


  • 0
    A



    class deque(list):
    def shift(self):
    r = self[0]
    super(deque, self).remove(r)
    return r

    class Solution:
    # @param root, a tree node
    # @return nothing
    def connect(self, root):
    if root is not None:
    q = deque([(root, 0)])
    while(len(q) > 0):
    p, n = q.shift()
    p.next = q[0][0] if len(q) > 0 and n == q[0][1] else None
    q.extend([(x, n+1) for x in [p.left, p.right] if x is not None])


Log in to reply
 

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