題目：

給定二叉樹的根節點root,請將它展開為一個單鏈表：

展開后的單鏈表應該使用同樣的TreeNode,其中right子指針指向鏈表中的下一個節點，而左子指針始終為空

展開后的單鏈表應該與二叉樹先序遍歷順序相同

---

方法一：二叉樹的前序遍歷?

將二叉樹展開為單鏈表之后，單鏈表中的節點順序即為二叉樹的前序遍歷訪問各節點的順序。因此，可以對二叉樹進行前序遍歷，獲得各節點被訪問到的順序。由于將二叉樹展開為鏈表之后會破壞二叉樹的結構，因此在前序遍歷結束之后更新每個節點的左右子節點的信息，將二叉樹展開為單鏈表。

通過遞歸實現前序遍歷

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def flatten(self, root):""":type root: Optional[TreeNode]:rtype: None Do not return anything, modify root in-place instead."""preorderList=[]#創建一個空列表,用于存儲二叉樹的所有節點def preorderTraversal(root):#遞歸函數，用于對樹進行前序遍歷if root: #前序遍歷的順序是：根 -> 左 -> 右。preorderList.append(root)preorderTraversal(root.left)preorderTraversal(root.right)preorderTraversal(root)size=len(preorderList)#二叉樹的節點總數for i in range(1,size): #從第二個節點開始，直到最后一個節點。因為鏈表的第一個節點已經由根節點 root 來表示prev,curr=preorderList[i-1],preorderList[i]#取當前節點 curr 和前一個節點 prevprev.left=None#將 prev 節點的左指針設置為 Noneprev.right=curr #將 prev 節點的右指針指向 curr

通過迭代的方式實現前序遍歷

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def flatten(self, root):""":type root: Optional[TreeNode]:rtype: None Do not return anything, modify root in-place instead."""preorderList = []  # 初始化一個空列表用于存儲二叉樹的節點stack = []  # 初始化一個空棧用于存儲遍歷過程中暫時訪問的節點node = root# 前序遍歷二叉樹while node or stack:while node:preorderList.append(node)  # 將當前節點添加到列表中stack.append(node)  # 將當前節點添加到棧中node = node.left  # 繼續遍歷左子樹node = stack.pop()  # 當左子樹遍歷結束時，從棧中彈出一個節點，這個節點是待訪問的右子節點（即上一個節點的右子樹）node = node.right  # 繼續訪問右子樹# 構建鏈表（右子樹按前序遍歷順序連接）size = len(preorderList)for i in range(1, size):  # 從第二個節點開始（因為第一個節點已經是鏈表的頭節點）prev, curr = preorderList[i - 1], preorderList[i]prev.left = None  # 清空左子樹prev.right = curr  # 將前一個節點的右指針指向當前節點

時間復雜度：O(n)，其中 n 是二叉樹的節點數。前序遍歷的時間復雜度是 O(n)，前序遍歷之后，需要對每個節點更新左右子節點的信息，時間復雜度也是 O(n)。

空間復雜度：O(n)，其中 n 是二叉樹的節點數。空間復雜度取決于棧（遞歸調用棧或者迭代中顯性使用的棧）和存儲前序遍歷結果的列表的大小，棧內的元素個數不會超過 n，前序遍歷列表中的元素個數是 n

---

方法三：尋找前驅節點

前序遍歷訪問各節點的順序是根節點、左子樹、右子樹。如果一個節點的左子節點為空，則該節點不需要進行展開操作。。如果一個節點的左子節點不為空，則該節點的左子樹中的最后一個節點被訪問之后，該節點的右子節點被訪問。該節點的左子樹中最后一個被訪問的節點是左子樹中的最右邊的節點，也是該節點的前驅節點。因此，問題轉化成尋找當前節點的前驅節點。

對于當前節點，如果其左子節點不為空，則在其左子樹中找到最右邊的節點，作為前驅節點,，將當前節點的右子節點賦給前驅節點的右子節點，然后將當前節點的左子節點賦給當前節點的右子節點，并將當前節點的左子節點設為空。對當前節點處理結束后，繼續處理鏈表中的下一個節點，直到所有節點都處理結束。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def flatten(self, root):""":type root: Optional[TreeNode]:rtype: None Do not return anything, modify root in-place instead."""curr=rootwhile curr:if curr.left:predecessor=nxt=curr.left#用來找到左子樹中最右的節點while predecessor.right:#找到左子樹中的最右節點predecessor=predecessor.right #向右移動，尋找最右邊的節點predecessor.right=curr.right#找到左子樹中的最右節點后,將當前節點的右子樹連接到左子樹的最右節點上curr.left=None     #當前節點的左子樹被置為curr.right=nxt#將當前節點的右指針指向左子樹的根節點curr=curr.right #使curr移動到下一個節點（即當前右子樹的第一個節點），繼續遍歷   

時間復雜度：O(n)其中?n?是二叉樹的節點數。展開為單鏈表的過程中，需要對每個節點訪問一次，在尋找前驅節點的過程中，每個節點最多被額外訪問一次

空間復雜度：O(1)

源自力扣官方題解
?