117.py

'''
 Given a binary tree

 struct TreeLinkNode {
 TreeLinkNode *left;
 TreeLinkNode *right;
 TreeLinkNode *next;
 }
 Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

 Initially, all next pointers are set to NULL.

 Example:

 Given the following binary tree,

 1
 / \
 2 3
 / \ \
 4 5 7
 After calling your function, the tree should look like:

 1 -> NULL
 / \
 2 -> 3 -> NULL
 / \ \
 4-> 5 -> 7 -> NULL
'''

# Definition for binary tree with next pointer.
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None

classSolution:
# @param root, a tree link node
# @return nothing
defconnect(self, root):
ifroot==None:
return
queue= [root]
queue.append(None)

whilequeue:
front=queue.pop(0)
iffrontisnotNone:
front.next=queue[0]
iffront.left:
queue.append(front.left)
iffront.right:
queue.append(front.right)
elifqueue:
queue.append(None)


# Definition for binary tree with next pointer.
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None

classSolution:
# @param root, a tree link node
# @return nothing
defconnect(self, root):
ifnotroot:
returnNone

root.next=None

whileroot:
temp=root
whiletemp:
iftemp.left:
iftemp.right:
temp.left.next=temp.right
else:
temp.left.next=self.getNext(temp)
iftemp.right:
temp.right.next=self.getNext(temp)

temp=temp.next
ifroot.left:
root=root.left
elifroot.right:
root=root.right
else:
root=self.getNext(root)

defgetNext(self, node):
node=node.next
whilenode:
ifnode.left:
returnnode.left
ifnode.right:
returnnode.right
node=node.next
returnNone