二叉樹轉雙向鏈表：中序遍歷就地轉換的三種實現

問題定義

將一棵二叉搜索樹（或普通二叉樹）就地轉換為排序雙向鏈表：

• 左指針 → 前驅（prev）
• 右指針 → 後繼（next）
• 中序遍歷順序即鏈表順序
• 返回鏈表頭節點（最小值）

方法一：遞歸 + 全局尾指針（最直觀）

TreeNode *prev = NULL, *head = NULL;

void inorder(TreeNode *root) {
    if (!root) return;
    inorder(root->left);
    
    // 處理當前節點
    root->left = prev;
    if (prev) prev->right = root;
    else      head = root;       // 首個節點為頭
    prev = root;
    
    inorder(root->right);
}

TreeNode* treeToDoublyList(TreeNode* root) {
    inorder(root);
    // 若需循環雙向鏈表，補上：
    // head->left = prev; prev->right = head;
    return head;
}

時間 O(n)，空間 O(h)（遞歸棧，h 為樹高）。

方法二：Morris 中序遍歷（O(1) 空間）

TreeNode* treeToDoublyList(TreeNode* root) {
    TreeNode *cur = root, *prev = NULL, *head = NULL;
    while (cur) {
        if (!cur->left) {
            // 訪問 cur
            cur->left = prev;
            if (prev) prev->right = cur;
            else      head = cur;
            prev = cur;
            cur = cur->right;
        } else {
            // 找前驅
            TreeNode *pre = cur->left;
            while (pre->right && pre->right != cur) pre = pre->right;
            if (!pre->right) {
                pre->right = cur;      // 建立線索
                cur = cur->left;
            } else {
                pre->right = NULL;     // 恢復樹結構
                // 訪問 cur
                cur->left = prev;
                if (prev) prev->right = cur;
                else      head = cur;
                prev = cur;
                cur = cur->right;
            }
        }
    }
    return head;
}

利用葉節點右指針為空的特性建立「線索」，無需棧，空間 O(1)。

方法三：分治遞歸返回頭尾（函數式風格）

struct Pair { TreeNode *head, *tail; };

Pair convert(TreeNode *root) {
    if (!root) return {NULL, NULL};
    Pair L = convert(root->left);
    Pair R = convert(root->right);
    
    root->left = L.tail;
    if (L.tail) L.tail->right = root;
    root->right = R.head;
    if (R.head) R.head->left = root;
    
    return { L.head ? L.head : root, R.tail ? R.tail : root };
}

TreeNode* treeToDoublyList(TreeNode* root) {
    return convert(root).head;
}

每層返回子鏈表頭尾，當前節點在中間串聯，邏輯清晰，無全局變量。

驗證與測試

void printList(TreeNode *head) {
    TreeNode *p = head;
    while (p) {
        printf("%d ", p->val);
        p = p->right;
    }
    puts("");
    // 反向驗證
    while (p && p->left) p = p->left;
    while (p) {
        printf("%d ", p->val);
        p = p->left;
    }
    puts("");
}

總結對比