劍指 Offer 專題：二叉搜索樹轉雙向鏈表（九度 OJ 1503）完整解析

題目描述

輸入一棵二叉搜索樹，將其轉換為一個排序的雙向鏈表。要求不能創建任何新節點，只能調整樹中節點指針的指向。

輸入格式

輸入可能包含多個測試樣例。每個測試案例的第一行為一個數 n (0 < n < 1000)，代表測試樣例的個數。接下來的 n 行，每行為一個二叉搜索樹的先序遍歷序列，其中左右子樹若為空則用 0 代替。

輸出格式

對應每個測試案例，輸出將二叉搜索樹轉換成排序的雙向鏈表後，從鏈表頭至鏈表尾的遍歷結果。

樣例

輸入： 1 2 1 0 0 3 0 0
輸出： 1 2 3

解題思路

這道題的核心在於中序遍歷。二叉搜索樹的中序遍歷結果天然有序，我們只需在遍歷過程中調整指針，將樹節點串成雙向鏈表即可。

關鍵步驟

1. 建樹：根據先序遍歷序列遞歸構建二叉搜索樹，遇到 0 表示空節點。
2. 中序遍歷轉換：維護一個指針 pLast 指向已轉換鏈表的尾節點。每次訪問節點時，將其 lchild 指向 pLast，若 pLast 不為空則將其 rchild 指向當前節點，最後更新 pLast 為當前節點。
3. 找鏈表頭：轉換完成後，pLast 指向尾節點，沿 lchild 向左遍歷即可找到頭節點。

圖解過程

完整代碼實現

#include <stdio.h>
#include <stdlib.h>

typedef struct btree {
    int data;
    struct btree *lchild, *rchild;
} BTree;

void createTree(BTree **b);
BTree *convert(BTree *b);
void convertNode(BTree *b, BTree **p);

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        BTree *b = (BTree *)malloc(sizeof(BTree));
        createTree(&b);
        BTree *head = convert(b);
        while (head != NULL) {
            printf("%d ", head->data);
            head = head->rchild;
        }
        printf("\n");
    }
    return 0;
}

/* 遞歸建樹：按先序序列構建 BST */
void createTree(BTree **b) {
    int m;
    scanf("%d", &m);
    if (m == 0) {
        *b = NULL;
    } else {
        BTree *s = (BTree *)malloc(sizeof(BTree));
        s->data = m;
        s->lchild = NULL;
        s->rchild = NULL;
        *b = s;
        createTree(&((*b)->lchild));
        createTree(&((*b)->rchild));
    }
}

/* 入口函數：返回雙向鏈表頭節點 */
BTree *convert(BTree *b) {
    BTree *pLast = NULL;
    convertNode(b, &pLast);
    BTree *phead = pLast;
    while (phead != NULL && phead->lchild != NULL)
        phead = phead->lchild;
    return phead;
}

/* 核心遞歸：中序遍歷並調整指針 */
void convertNode(BTree *b, BTree **p) {
    if (b == NULL) return;
    BTree *pnow = b;
    if (b->lchild != NULL) convertNode(b->lchild, p);
    pnow->lchild = *p;
    if (*p != NULL) (*p)->rchild = pnow;
    *p = pnow;
    if (b->rchild != NULL) convertNode(b->rchild, p);
}

複雜度分析

• 時間複雜度：O(n)，每個節點恰好被訪問一次。
• 空間複雜度：O(h)，遞歸棧深度等於樹高，最壞情況 O(n)，平均 O(log n)。

常見坑點提醒

• 輸入中 0 代表空節點，建樹時必須正確處理。
• 轉換過程不可分配新節點，只能改指針。
• 最後輸出時從頭節點沿 rchild 遍歷，別搞反方向。