<div>Given the root of a binary tree, flatten the tree into a "linked list": * The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. * The "linked list" should be in the same order as a pre-order traversal of the binary tree. Example 1: 
<pre>Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6] </pre>
Example 2:
<pre>Input: root = [] Output: [] </pre>
Example 3:
<pre>Input: root = [0] Output: [0] </pre>
Constraints: * The number of nodes in the tree is in the range [0, 2000]. * -100 <= Node.val <= 100 Follow up: Can you flatten the tree in-place (with O(1) extra space)?</div>
题目大意：
将二叉树转成以右节点相连的LL
解题思路：
递归需要知道左右递归末尾节点，这样才可以将右节点的首节点接到左节点的末尾。所以递归函数输入是root，返回LL末尾节点
解题步骤：
N/A
注意事项：
- 递归函数输入是root，返回LL末尾节点
- 如果left_end是空，也就是没有左节点，就不用交换。返回right_end, left_end, root三者中非空者。
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18def flatten(self, root: TreeNode) -> None:
self.dfs(root)
def dfs(self, root: TreeNode) -> None:
if not root:
return None
left_end = self.dfs(root.left)
right_end = self.dfs(root.right)
if left_end: # remember
left_end.right = root.right
root.right, root.left = root.left, None
if right_end:
return right_end
elif left_end:
return left_end
else:
return root
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
