题目：

给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [0]
输出：[0]

提示：
树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100

解法一：后序遍历+头插法

# 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:head=Nonedef flatten(self, root: Optional[TreeNode]) -> None:"""Do not return anything, modify root in-place instead."""if root is None:return self.flatten(root.right)self.flatten(root.left)# 当前节点左子节点必须为空root.left=None# 当前节点的右子节点指向头节点root.right=self.head# 将当前节点定义为头节点self.head=root

思路：
先把按照后序遍历，右子树->左子树->根节点，比如6-5-4-3-2-1，从右子树最后一个节点6开始，后续节点依次指向前一个节点，1-2-3-4-5-6。
解释最后三步：

📌 (1) root.left = None
题目要求最终树变成右链表，左子树必须为空，所以直接清空。

📌 (2) root.right = self.head
self.head 是 已经处理完的“后半部分链表”的头节点。
现在我们要把 root 接到这个链表的前面。
所以让 root.right 指向 self.head，相当于把 root 插到链表头部。
📌 (3) self.head = root
更新头节点为 root，因为 root 现在是链表最前面的节点。

---

解法二:分治

# 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: Optional[TreeNode]) -> None:"""Do not return anything, modify root in-place instead."""if root is None:return None# 左子树尾节点left_tail = self.flatten(root.left)# 右子树尾节点right_tail = self.flatten(root.right)if left_tail:# 左子树的尾要指向右子树的头left_tail.right = root.right# 根节点的尾要指向左子树的头root.right=root.left# 清空左指针root.left=Nonereturn right_tail or left_tail or root

核心逻辑：拼接三部分
我们要把整棵树展平，顺序是：

root → 左子树链表 → 右子树链表

所以我们需要：

• 把 root 的右指针指向左子树链表的头（即 root.left）
• 把左子树链表的尾（left_tail）指向右子树链表的头（即原来的 root.right）
• 清空左子树指针