> For the complete documentation index, see [llms.txt](https://ryukiedev.gitbook.io/wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](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).

# 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
```