Flatten Binary Tree to Linked List

Flatten a binary tree to a fake "linked list" in pre-order traversal.

Here we use the_right_pointer in TreeNode as the_next_pointer in ListNode.

Example

              1
               \
     1          2
    / \          \
   2   5    =>    3
  / \   \          \
 3   4   6          4
                     \
                      5
                       \
                        6

Traverse Pre-Order

首先来看递归版本的，思路是先利用DFS的思路找到最左子节点，然后回到其父节点，我们需要一个 pointer last来保存父节点，然后

我们需要把右子树临时保存起来，因为把左子树添加到右子树位置时会把原先的右子树覆盖掉。再然后将原左子结点连上父节点的右子节点上，然后再把原右子节点连到新右子节点的右子节点上，然后再回到上一父节点做相同操作。

     1
    / \
   2   5
  / \   \
 3   4   6

     1
    / \
   2   5
    \   \
     3   6
      \    
       4

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        this.val = val
        this.left, this.right = None, None
"""
class Solution:
    # @param root: a TreeNode, the root of the binary tree
    # @return: nothing
    last = None
    def flatten(self, root):
        # write your code here
        if not root:
            return
        if self.last!=None:
            self.last.left = None
            self.last.right = root

        self.last = root
        # 临时保存右节点
        right = self.last.right
        # 进入左子树
        self.flatten(root.left)
        # 进入原来的右子树
        self.flatten(right)

递归后序遍历（Recursive Postorder Traversal）

这里对标准的递归后序遍历稍作改动，由“左-右-根”变更为“右-左-根”，详见代码。

# 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.
        """
        self.pointer = None
        def traverse(root):
            if not root: return
            traverse(root.right)
            traverse(root.left)
            root.right = self.pointer
            root.left = None
            self.pointer = root
        traverse(root)

没写完！！！！！