【python/M/114】Flatten Binary Tree to Linked List

题目

基本思路

首先呢，我们要来理解题意，按先序遍历的顺序将一棵二叉树变成一个类似的单链表。
我们这么做：首先对树进行先序遍历同时将所有节点错放在一个数组中，数组中元素类型为一个个TreeNode，然后遍历这个数组，将元素依次连接起来，记住要将左子树节点变成空。

实现代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        # 充分理解展开后列表的这个形式，不是个单链表！
        ans = []
        def preOrder(root):
            if not root:
                return 
            ans.append(root)
            preOrder(root.left)
            preOrder(root.right)
        preOrder(root)
        p = root
        for i in range(1,len(ans)):
            p.left = None
            p.right = ans[i]
            p = ans[i]