/*
 * 演算法 / 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
    }
}