非原地操作：114.二叉树展开为链表

给定一个二叉树，原地将它展开为一个单链表。

例如，给定二叉树1/ \2   5/ \   \
3   4   6
将其展开为：1\2\3\4\5\6

1、题目分析

将一个二叉树给它拆开，拆成链表。其实这个题目要求是原地操作，也就是时间复杂度是O(1)。但是原地操作我没看明白，所以用了一个O(n)的方法去解决这个问题。可以进行先序的遍历操作，然后把结构存放起来，在构建一个二叉树就可以了。

2、解题分析

• 前序遍历二叉树
• 构建一个只有右子树的二叉树

3、代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def flatten(self, root: TreeNode) -> None:"""Do not return anything, modify root in-place instead."""if not root:return rootd = []def helper(root):if not root:return d.append(root.val)helper(root.left)helper(root.right)helper(root)i = 1 #令左子树为空root.left = Nonep = rootwhile i < len(d):p.right = TreeNode(d[i])p = p.righti += 1

总结：复习了二叉树的前序遍历；但是没有达到题目要求的原地操作。