二叉搜索树与双向链表

619 字

3 分钟

二叉搜索树与双向链表

2021-10-20

2026-10-12

数据结构与算法

「剑指Offer」Swift

题目#

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

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

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

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

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

来源：力扣（LeetCode）

分析#

题解#

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

代码#

1
var head: TreeNode?, last: TreeNode?
2

3
func treeToDoublyList(root: TreeNode) -> TreeNode {
4
    handle(root: root)
5
    last?.right = head
6
    head?.left = last
7
    return root
8
}
9

10
func handle(root: TreeNode) -> TreeNode {
11
    if let left = root.left {
12
        if let rightOfLeft = left.right {
13
            let node = handle(root: rightOfLeft)
14
            root.left = node
15
            node.left = left
16
            node.right = root
17
        }
18

19
        if let leftOfLeft = left.left, leftOfLeft.left == nil {
20
            leftOfLeft.right = left
21
            head = leftOfLeft
22
        }
23
    }
24

25
    if let right = root.right {
26
        if let leftOfRight = right.left {
27
            let node = handle(root: leftOfRight)
28
            root.right = node
29
            node.right = right
30
            node.left = root
31
        }
32

33
        if let rightOfRight = right.right, rightOfRight.right == nil {
34
            rightOfRight.left = right
35
            last = rightOfRight
36
        }
37
    }
38

39
    return root
40
}

用例#

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

9
t4.left = t2
10
t4.right = t6
11

12
t2.left = t1
13
t2.right = t3
14

15
t6.left = t5
16
t6.right = t7
17

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

20
func log(root: TreeNode) {
21
    if let left = root.left {
22
        print("\(root.val)左：\(left.val)")
23
    }
24
    else {
25
        print("\(root.val)左：nil")
26
    }
27

28
    if let right = root.right {
29
        print("\(root.val)右：\(right.val)")
30
    }
31
    else {
32
        print("\(root.val)右：nil")
33
    }
34
}
35

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

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

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

输出：

1
1左：nil
2
1右：nil
3
2左：1
4
2右：3
5
3左：nil
6
3右：nil
7
4左：2
8
4右：6
9
5左：nil
10
5右：nil
11
6左：5
12
6右：7
13
7左：nil
14
7右：nil
15
=== 双向转换 ===
16
1左：7
17
1右：2
18
2左：1
19
2右：3
20
3左：2
21
3右：4
22
4左：3
23
4右：5
24
5左：4
25
5右：6
26
6左：5
27
6右：7
28
7左：6
29
7右：1

序列化二叉树

应用图标圆角