題目：

給你二叉樹的根結點 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）
• 清空左子樹指針