426. Convert Binary Search Tree to Sorted Doubly Linked List

──────────────────────────────────────────────────────────────────────

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

思路

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

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

所以整題就是「中序遍歷，邊走邊把節點接起來」。不需要新的演算法，只是把 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，原本的左子樹就找不回來了 —— 所以順序不能動，這是原地改指標題目的通則。

解題方向

"""
# 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 常被搞混，但兩者的順序需求不同：

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

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

同樣靠中序性質的題目：94. Inorder Traversal、173. BST Iterator（把中序拆成可暫停的迭代器）、230. Kth Smallest Element in a BST、98. Validate Binary Search Tree。整理見 Tree 遍歷模板。

複雜度

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

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

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