class Solution: # @param root, a tree node # @return nothing def connect(self, root): if not root: return None tmpLeft,queue=root, if tmpLeft.left and tmpLeft.right: queue.append(tmpLeft.left) queue.append(tmpLeft.right) k,label,range=1,0,1 # use a queue to perform level order traverse while queue: tmpRight=queue.pop(0) if tmpRight.left and tmpRight.right: queue.append(tmpRight.left) queue.append(tmpRight.right) if k<label+range: # the combination of k label and range to determine whether the current note is located at the right edge tmpLeft.next=tmpRight else: tmpLeft.next=None label+=range # the number of nodes is doubled compared the number of nodes of previous level range+=range tmpLeft=tmpRight k+=1 tmpLeft.next=None
The code is based on the level order traverse. Any comments would be appreciated!
The question asked for constant extra space. I'm afraid as long as you use a queue, the space complexity is not constant anymore.