# 题目链接
# 题目描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

# 解题思路
package main
import "fmt"
//将BST转化为双向循环链表,不允许新建节点
//为防止歧义,左指针表示双链表向前指,右指针表示双链表向后指
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
var pre *TreeNode //必须在全局变量上才可以实现
func treeToDoublyList(root *TreeNode) *TreeNode {
if root == nil {
return root
}
helper(root)
head, tail := root, root
for head.Left != nil {
head = head.Left
}
for tail.Right != nil {
tail = tail.Right
}
head.Left = tail
tail.Right = head
return head
}
func helper(root *TreeNode) {
if root == nil {
return
}
helper(root.Left)
if pre != nil {
root.Left = pre
pre.Right = root
}
pre = root
helper(root.Right)
}
func main() {
root := &TreeNode{4, nil, nil}
node1 := &TreeNode{2, nil, nil}
node2 := &TreeNode{5, nil, nil}
node3 := &TreeNode{1, nil, nil}
node4 := &TreeNode{3, nil, nil}
root.Left = node1
root.Right = node2
node1.Left = node3
node1.Right = node4
head := treeToDoublyList(root)
tail := head.Left
//从头开始遍历
for i := 0; i <= 9; i++ {
fmt.Printf("%d\t", head.Val)
head = head.Right
}
//从尾开始遍历
for i := 0; i <= 9; i++ {
fmt.Printf("%d\t", tail.Val)
tail = tail.Left
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
当然,为了方便,也可以直接将pre作为引用变量传进来(它本身就是引用,弄个双重指针就欧克)
之前一直觉得多重指针没用,现在看来,真香~~~
func treeToDoublyList(root *TreeNode) *TreeNode {
if root == nil {
return root
}
var pre *TreeNode
helper(root, &pre)//使用多重指针即可
head, tail := root, root
for head.Left != nil {
head = head.Left
}
for tail.Right != nil {
tail = tail.Right
}
head.Left = tail
tail.Right = head
return head
}
func helper(root *TreeNode, pre **TreeNode) {
if root == nil {
return
}
helper(root.Left, pre)
if (*pre) != nil {
root.Left = (*pre)
(*pre).Right = root
}
(*pre) = root
helper(root.Right, pre)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30