114. Flatten Binary Tree to Linked List

方法一：用preorder traversal 的方法，把每一个node都存到一个list里面，因为每次存的都是完整的root，所以在list里的每一个值都有完整的TreeNode的属
性。然后从前到后遍历每一个root，temp[i].right = temp[i+1]; temp.left = None
class Solution:
    def preorder(self, root, ls):
        if not root:
            return

        ls.append(root)
        self.preorder(root.left, ls)
        self.preorder(root.right, ls)

    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        if not root:
            return None

        temp = []
        self.preorder(root, temp)

        for i in range(0, len(temp)-1):
            temp[i].right = temp[i+1]
            temp[i].left = None

方法二：方法二其实比方法一复杂，但是是另一种实现的方法。再次方法中，preorder不再是用recursive来实现，而是用interaction的方法。先用preorder把左子      树变成一个linked list。然后把右子树变成一个linked list, 之后把root -> left -> right 连起来。最后root.left = None
class Solution:
    def preorder(self, root):
        if not root:
            return None

        head = TreeNode(0)
        temp = head

        st = []
        st.append(root)
        while st:
            node = st.pop()
            temp.right = TreeNode(node.val)
            temp = temp.right

            if node.right:
                st.append(node.right)
            if node.left:
                st.append(node.left)

        return head.right


    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        if not root:
            return None

        left = self.preorder(root.left)
        right = self.preorder(root.right)

        if left:
            temp = left
            while temp.right:
                temp = temp.right

            temp.right = right
            root.right = left

        else:
            root.right = right

        root.left = None