flattenBinaryTreeToLinkedList.py

#  Given a binary tree, flatten it to a linked list in-place.
#
# For example,
# Given
#
#          1
#         / \
#        2   5
#       / \   \
#      3   4   6
#
# The flattened tree should look like:
#
#    1
#     \
#      2
#       \
#        3
#         \
#          4
#           \
#            5
#             \
#              6
#
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        if not root:    return
        st = [root]
        dummy = TreeNode(0)
        n = dummy
        while(st):
            n.right = st.pop()
            n.left = None
            n = n.right
            if n.right: st += [n.right]
            if n.left:  st += [n.left]
        return