114. Flatten Binary Tree to Linked List

題目 / Problem

中文： 給定一棵二元樹的根節點 root，請把這棵樹「攤平」成一個「鏈結串列」： - 攤平後仍然使用同一個 TreeNode 類別，但每個節點的 right 指標指向下一個節點，而 left 指標一律設為 null。 - 這個「鏈結串列」的節點順序必須和二元樹的前序遍歷（pre-order：根 → 左 → 右）順序完全一致。

English: Given the root of a binary tree, flatten it into a "linked list": - The list reuses the same TreeNode class; each node's right points to the next node and every left is set to null. - The order of the list must match the pre-order traversal (root → left → right) of the tree.

限制 / Constraints - 節點數量範圍 / number of nodes in range [0, 2000]. - -100 <= Node.val <= 100. - 進階 / Follow-up: 能否做到原地攤平、只用 O(1) 額外空間？ / Can you do it in-place with O(1) extra space?

範例 / Example

Input:  root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

原本的樹 / the original tree:

      1
     / \
    2   5
   / \   \
  3   4   6

前序遍歷是 1 → 2 → 3 → 4 → 5 → 6，攤平後所有節點只靠 right 串成一條往右的鏈。 Pre-order is 1 → 2 → 3 → 4 → 5 → 6; after flattening they form one rightward chain.

名詞解釋 / Glossary

• 二元樹 / Binary tree：每個節點最多有兩個子節點（left 與 right）的樹狀結構。/ A tree where each node has at most two children, left and right.
• 前序遍歷 / Pre-order traversal：先訪問「根」，再遞迴訪問「左子樹」，最後「右子樹」，順序是 根→左→右。/ Visit the root first, then recurse into the left subtree, then the right subtree (root → left → right).
• 原地修改 / In-place：直接改動原本的節點指標，不另外開一個大的陣列或串列來存資料，因此額外空間很小。/ Rearrange the existing node pointers directly instead of allocating a separate big container, so extra memory stays tiny.
• 指標 / Pointer：一個變數，裡面存的是「某個節點的記憶體位址」。在 C 用 -> 存取它指向的成員，NULL 表示不指向任何東西。/ A variable holding the memory address of a node; in C we use -> to reach its members, and NULL means "points to nothing".
• 最右節點 / Rightmost node：從某個節點出發，一直往 right 走到不能再走的那個節點。它是該子樹在前序中「最後被訪問」的位置。/ The node reached by following right as far as possible; in a subtree it is the last node visited in pre-order.
• Morris 式重接 / Morris-style rewiring：一種不用堆疊或遞迴、只靠改指標就能遍歷/重組樹的技巧，因此可達 O(1) 空間。/ A technique that reorganizes a tree using only pointer edits — no stack or recursion — achieving O(1) space.

思路

中文：最直覺的暴力法是先做一次前序遍歷，把所有節點依序存進一個陣列（或用遞迴收集），再從頭到尾把每個節點的 left 設成 NULL、right 設成下一個節點。這樣完全正確，但需要一個大小為 n 的額外容器，空間是 O(n)，沒有達到進階要求。我們想更省空間。關鍵觀察在提示裡：攤平後每個節點的 right 就是它前序的「下一個」。想像目前站在節點 cur。如果 cur 沒有左子樹，那前序的下一個自然就是它原本的右子樹，什麼都不用動，直接往右走。如果 cur 有左子樹，前序順序會是：先走完整個左子樹，才輪到右子樹。所以我們要把「原本的右子樹」接到「左子樹前序最後一個節點」的後面——而左子樹前序的最後一個節點，正好是左子樹一路往 right 走到底的那個「最右節點」。於是做三件事：找到左子樹的最右節點 pre；把 cur->right（原右子樹）接到 pre->right；把左子樹整個搬到 cur->right，並把 cur->left 設成 NULL。做完後 cur 往 right 前進，重複直到走完。因為左子樹被「插」進了正確位置，之後往右走時一定會依前序碰到每個節點。這個做法只用了幾個指標變數，空間 O(1)，是不變量「cur 左邊（含 cur）都已經排好、且順序正確」在支撐它。

English: The brute-force idea is to run a pre-order traversal, collect every node into an array (or a recursive list), then relink them: set each node's left to NULL and right to the next collected node. It is correct but needs an O(n) container, so it misses the follow-up's O(1) goal. The hint points the way: after flattening, each node's right is simply its pre-order successor. Stand at a node cur. If cur has no left child, its pre-order successor is already its right subtree — do nothing, just move right. If cur does have a left subtree, pre-order says we must finish the entire left subtree before the right subtree. So we splice the original right subtree onto the end of the left subtree. That "end" is the left subtree's rightmost node pre (follow right to the bottom), which is exactly the last node visited in the left subtree's pre-order. Concretely: find pre; attach cur->right to pre->right; move the whole left subtree to cur->right; set cur->left = NULL. Then advance cur to its (new) right and repeat. Because each left subtree is inserted at precisely the right spot, walking rightward afterwards hits every node in pre-order. Only a handful of pointer variables are used — O(1) space — held together by the invariant that everything at and before cur is already correctly ordered.

逐步走查 / Walkthrough

輸入 / Input: [1,2,5,3,4,null,6]

      1
     / \
    2   5
   / \   \
  3   4   6

每一步 cur->left 都被清成 NULL，最後整棵樹變成一條只往右的鏈。 At every step cur->left becomes NULL, and the whole tree ends up as a single rightward chain.

Solution — C

/*
 * 演算法 / Algorithm:
 * 走訪每個節點 cur；若有左子樹，找到左子樹的「最右節點」pre，
 * 把 cur 原本的右子樹接到 pre->right，再把左子樹移到 cur->right，清空 cur->left。
 * Walk each node; if it has a left subtree, find that subtree's rightmost node `pre`,
 * splice cur's old right subtree onto pre->right, move the left subtree to cur->right,
 * and null out cur->left. Only O(1) extra pointers are used.
 */

// LeetCode 已定義 TreeNode / TreeNode is predefined by LeetCode:
// struct TreeNode { int val; struct TreeNode *left, *right; };

void flatten(struct TreeNode* root) {
    struct TreeNode* cur = root;          // cur 是目前處理的節點 / cur is the node we are processing now
    while (cur != NULL) {                 // 一直走到沒有節點為止 / keep going until we run off the chain
        if (cur->left != NULL) {          // 只有「有左子樹」時才需要重接 / rewiring is only needed when a left subtree exists
            struct TreeNode* pre = cur->left;   // pre 從左子樹的根開始 / start pre at the root of the left subtree
            while (pre->right != NULL) {  // 一路往右走到底 / walk right as far as possible
                pre = pre->right;         // pre 最後停在左子樹的「最右節點」/ pre ends at the left subtree's rightmost node
            }
            pre->right = cur->right;      // 把 cur 原本的右子樹接到左子樹尾端 / attach cur's old right subtree after the left subtree
            cur->right = cur->left;       // 左子樹整個搬到 cur 的右邊 / move the entire left subtree to cur's right
            cur->left = NULL;             // 依題目要求，left 必須清成 NULL / left must become NULL as required
        }
        cur = cur->right;                 // 往前序的下一個節點前進 / advance to the next node in pre-order
    }
}

Solution — C++

/*
 * 演算法 / Algorithm:
 * 對每個節點 cur，若有左子樹，找左子樹最右節點 pre，把 cur 的右子樹接到 pre->right，
 * 再把左子樹移到右邊並清空左指標。原地完成，O(1) 額外空間。
 * For each node cur with a left subtree, find the left subtree's rightmost node pre,
 * hang cur's right subtree off pre->right, then move the left subtree to the right
 * and clear the left pointer. Done in place with O(1) extra space.
 */

// LeetCode 已定義 TreeNode / TreeNode is predefined by LeetCode.
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* cur = root;             // cur 指向目前處理的節點 / cur points at the node we process now
        while (cur != nullptr) {          // nullptr 是 C++ 的空指標 / nullptr is C++'s null pointer literal
            if (cur->left != nullptr) {   // 有左子樹才需要搬動 / only rewire when a left subtree exists
                TreeNode* pre = cur->left;      // 從左子樹的根出發 / begin at the left subtree's root
                while (pre->right != nullptr) { // 沿著 right 一直往下 / follow right to the bottom
                    pre = pre->right;     // pre 停在左子樹最右節點（前序最後一個）/ pre lands on the rightmost node (last in pre-order)
                }
                pre->right = cur->right;  // 舊的右子樹接到左子樹尾端 / splice the old right subtree onto the tail
                cur->right = cur->left;   // 左子樹移到右邊 / left subtree becomes the right subtree
                cur->left = nullptr;      // left 依規定清空 / clear left as the problem requires
            }
            cur = cur->right;             // 前進到下一個（前序）節點 / move to the next pre-order node
        }
    }
};

複雜度 / Complexity

• Time: O(n) — 每個節點最多被 cur 訪問一次，加上被當作某個左子樹的「最右節點」搜尋時經過；每條右邊界只會被走過常數次，總和仍是線性，n 是節點數。/ Each node is visited a constant number of times (once by cur, plus along a rightmost search); total work is linear in the number of nodes n.
• Space: O(1) — 只用了 cur、pre 兩個指標，沒有遞迴堆疊也沒有額外陣列。/ Only two pointers cur and pre; no recursion stack, no auxiliary array.

Pitfalls & Edge Cases

• 空樹 / Empty tree（root == NULL）：while 迴圈條件一開始就是 false，直接結束，安全回傳。/ The loop condition is false immediately, so we return safely with nothing to do.
• 只有一個節點 / Single node：沒有左子樹，只是原地往右走一步到 NULL，結果就是它自己。/ No left subtree; we simply step right into NULL, leaving the single node as the whole list.
• 忘記清空 left / Forgetting to clear left：題目要求所有 left 必須是 NULL；漏掉這行會讓輸出結構錯誤，即使數值順序看起來對。/ The problem mandates every left be NULL; skipping cur->left = nullptr produces a wrong structure even if values look right.
• 重接順序寫反 / Wrong order of the three rewires：必須先 pre->right = cur->right（保存舊右子樹），再 cur->right = cur->left；若先覆蓋 cur->right，原本的右子樹就遺失了。/ You must save the old right subtree (pre->right = cur->right) before overwriting cur->right; reversing them loses the right subtree entirely.
• 在錯的節點上找最右 / Finding rightmost on the wrong node：pre 要從 cur->left 出發沿 right 找，而不是從 cur 出發，否則會接錯位置造成環或亂序。/ Start pre at cur->left, not cur; otherwise the splice point is wrong and you can create a cycle or scramble the order.