---
title: "426. Convert Binary Search Tree to Sorted Doubly Linked List"
url: "https://laigary.com/interview/coding/426-convert-binary-search-tree-to-sorted-doubly-linked-list"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-26"
tags: ["Linked List", "Inorder Traversal", "Tree"]
---

# 426. Convert Binary Search Tree to Sorted Doubly Linked List

[426\. Convert Binary Search Tree to Sorted Doubly Linked List](https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/)

把一棵 BST 原地改成**排序好的循環雙向鏈結串列**。`left` 當作 `prev`、`right` 當作 `next`，而且頭尾要接起來成一個環。

## 思路

這題的第一個關卡是看穿它其實不難：

> **BST 的中序遍歷 = 遞增序列**，而「排序的鏈結串列」就是遞增序列。

所以整題就是「**中序遍歷，邊走邊把節點接起來**」。不需要新的演算法，只是把 [94. Binary Tree Inorder Traversal](/interview/coding/94-binary-tree-inorder-traversal) 裡「`res.append(node.val)`」那一步換成「接指標」。

第二個關卡是**接指標時需要記住什麼**。中序走到某個節點時，我要把它和「前一個走過的節點」連起來，所以需要一個 `tail` 變數持續指向「目前串列的最後一顆」。再加一個 `head` 記住最左邊那顆（第一個被走到的），最後才能把頭尾接成環。

於是規則變得很簡單：

- `tail` 還是空的 → 我就是最左邊那顆 → `head` 和 `tail` 都設成我
- `tail` 已經有了 → 把 `tail.right` 指向我、我的 `left` 指向 `tail`，然後 `tail` 前進到我

**注意 `dfs(node.left)` 必須在接指標之前呼叫。** 一旦開始改 `node.left`，原本的左子樹就找不回來了 —— 所以順序不能動，這是原地改指標題目的通則。

## 解題方向

```python
"""
# Definition for a Node.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return None
        head = None
        tail = None
        def dfs(node: 'Node'):
            nonlocal head, tail
            if node:
                dfs(node.left)
                if not tail:
                    # 如果還沒有尾巴，代表我們走到了最左邊的節點
                    # 這時候頭和尾巴都是此節點
                    head = node
                    tail = node
                else:
                    # 如果已經有尾巴了，這時候做兩件事情
                    # 第一：建立雙向連結
                    #     將目前的尾巴節點的右邊，指向現在的節點
                    #     將當前指向的節點的左邊，指向當前的尾巴
                    # 第二：尾巴節點向右移動
                    tail.right = node
                    node.left = tail
                    tail = tail.right
                dfs(node.right)
        dfs(root)
        head.left = tail
        tail.right = head
        return head
```

`nonlocal head, tail` 是重點：內層函式要**修改**外層的變數就必須宣告，只讀取則不用。這是樹的遞迴題最常用的技巧之一 —— 把狀態放在外層，遞迴函式專心走訪。

**空樹要提前 return。** 最後那兩行 `head.left = tail` 會在 `head` 是 `None` 時炸掉，所以開頭的 `if not root: return None` 不能省。

**`tail = tail.right` 和 `tail = node` 是等價的**（上一行才剛把 `tail.right` 設成 `node`）。寫成前者強調「尾巴往右移動一格」的語意，寫成後者比較直接，兩種都可以。

## 補充

**這題和 [114. Flatten Binary Tree to Linked List](/interview/coding/114-flatten-binary-tree-to-linked-list) 常被搞混**，但兩者的順序需求不同：

| | 用哪種遍歷 | 結果順序 |
|---|---|---|
| **426 這題** | **中序** | 遞增（因為是 BST） |
| 114 Flatten | **前序** | 前序順序，單向 |

會不一樣是因為 114 要的就是前序展開，而這題要的是排序 —— 而 BST 的排序順序只有中序給得出來。**「題目要什麼順序」決定了「用哪種遍歷」**，這是樹的題目第一個要問自己的問題。

**同樣靠中序性質的題目**：[94. Inorder Traversal](/interview/coding/94-binary-tree-inorder-traversal)、[173. BST Iterator](/interview/coding/173-binary-search-tree-iterator)（把中序拆成可暫停的迭代器）、[230. Kth Smallest Element in a BST](/interview/coding/230-kth-smallest-element-in-a-bst)、[98. Validate Binary Search Tree](/interview/coding/98-validate-binary-search-tree)。整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 複雜度

- 時間 $O(n)$ — 中序走訪每個節點一次，每次只做常數次指標賦值
- 空間 $O(h)$ — 遞迴堆疊；`head` / `tail` 是兩個變數，不隨輸入成長

其中 `n` 是節點數、`h` 是樹高（平衡樹 $O(\log n)$、斜樹 $O(n)$）。

**沒有建立任何新節點**，全部都是改原本節點的 `left` / `right`，所以是真正的原地轉換 —— 這也是題目說 "in place" 的意思。