# 36.二叉搜索树与双向链表

### 题目

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

![01](/files/0Q1LvmZm82bmR9ES7cEp)

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

![02](/files/7BxK9qFtvWjtAW7hwBA8)

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

来源：[力扣（LeetCode）](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof)

### 分析

### 题解

由于没有官方没有 Swift 的用例，这里自己写了用例来测试

#### 代码

```
var head: TreeNode?, last: TreeNode?

func treeToDoublyList(root: TreeNode) -> TreeNode {
    handle(root: root)
    last?.right = head
    head?.left = last
    return root
}

func handle(root: TreeNode) -> TreeNode {
    if let left = root.left {
        if let rightOfLeft = left.right {
            let node = handle(root: rightOfLeft)
            root.left = node
            node.left = left
            node.right = root
        }
        
        if let leftOfLeft = left.left, leftOfLeft.left == nil {
            leftOfLeft.right = left
            head = leftOfLeft
        }
    }
    
    if let right = root.right {
        if let leftOfRight = right.left {
            let node = handle(root: leftOfRight)
            root.right = node
            node.right = right
            node.left = root
        }
        
        if let rightOfRight = right.right, rightOfRight.right == nil {
            rightOfRight.left = right
            last = rightOfRight
        }
    }
    
    return root
}
```

#### 用例

```
let t1 = TreeNode(1)
let t2 = TreeNode(2)
let t3 = TreeNode(3)
let t4 = TreeNode(4)
let t5 = TreeNode(5)
let t6 = TreeNode(6)
let t7 = TreeNode(7)

t4.left = t2
t4.right = t6

t2.left = t1
t2.right = t3

t6.left = t5
t6.right = t7

let arr = [t1, t2, t3, t4, t5, t6, t7]

func log(root: TreeNode) {
    if let left = root.left {
        print("\(root.val)左：\(left.val)")
    }
    else {
        print("\(root.val)左：nil")
    }
    
    if let right = root.right {
        print("\(root.val)右：\(right.val)")
    }
    else {
        print("\(root.val)右：nil")
    }
}

arr.forEach { log(root: $0) }

print("=== 双向转换 ===")
treeToDoublyList(root: t4)

arr.forEach { log(root: $0) }
```

输出：

```
1左：nil
1右：nil
2左：1
2右：3
3左：nil
3右：nil
4左：2
4右：6
5左：nil
5右：nil
6左：5
6右：7
7左：nil
7右：nil
=== 双向转换 ===
1左：7
1右：2
2左：1
2右：3
3左：2
3右：4
4左：3
4右：5
5左：4
5右：6
6左：5
6右：7
7左：6
7右：1
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/36.-er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.