114. Flatten Binary Tree to Linked List

Flatten Binary Tree to Linked List

題目描述：給定一棵二元樹的根節點，將整棵樹「就地」展平成一個單向鏈結串列。展平後的鏈結串列應遵循前序遍歷（preorder）的順序，並且每個節點的 left 指標都應設為 null，right 指標指向鏈結串列中的下一個節點。

解題思路：使用類 Morris 遍歷的迭代方式，對每個擁有左子樹的節點執行以下操作：

1. 找到左子樹中最右邊的節點（也就是前序遍歷中緊接在左子樹之前、右子樹之後的「前驅節點」）。
2. 將當前節點原本的右子樹，接到這個最右節點的 right 上。
3. 將當前節點的 left 子樹移動到 right，並將 left 設為 null。
4. 移動到 right（原本的左子樹根節點）繼續處理。

這樣做的關鍵在於：前序順序為「根 → 左子樹 → 右子樹」，因此左子樹整體應排在右子樹之前。把右子樹接到左子樹最右端之後，再把左子樹移到右邊，就能在 O(n) 時間、O(1) 額外空間內完成展平。

時間複雜度：O(n) — 每個節點最多被訪問兩次：一次作為 cur 節點、一次作為尋找最右節點時經過的節點。整體遍歷次數線性於節點總數 n。

空間複雜度：O(1) — 迭代方式不使用遞迴呼叫堆疊，也不需要額外資料結構，僅使用常數個指標變數。

方法一：遞迴後序展平 將問題分解：先遞迴展平左子樹和右子樹，再把已展平的左子鏈串接到右子鏈頭部，並移到右側。時間複雜度 O(n)，空間複雜度 O(h)（h 為樹高，遞迴堆疊）。

方法二：前序遍歷存節點後重建 先以前序遍歷收集所有節點到陣列，再依序將每個節點的 right 設為下一個節點、left 設為 null。實作最直觀，但需要 O(n) 額外空間存放節點陣列。

方法三：使用明確 Stack 模擬前序 用 stack 模擬前序遍歷：每次 pop 節點後，將右子節點先入 stack、再將左子節點入 stack；用 prev 指標追蹤上一個處理的節點，即時接線。時間複雜度 O(n)，空間複雜度 O(h)。

1. 如果要求展平後的順序改為後序遍歷（postorder），解法需要如何調整？
2. 本題使用 Morris 遍歷達到 O(1) 空間，請問 Morris 遍歷的核心思想是什麼？它如何在不使用額外空間的情況下完成遍歷並恢復樹的結構？
3. 如果輸入的不是二元樹，而是 N 叉樹（每個節點可有任意多個子節點），如何設計類似的就地展平演算法？