题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
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
| import Foundation
//中序遍历，节点互指
class For27Solution {
var head:TreeNode?
var lastNode:TreeNode?
func convertTwoWayList(_ root:TreeNode?) -> TreeNode? {
convertSubList(root)
return head
}
func convertSubList(_ root:TreeNode?) {
if root == nil {
return
}
convertSubList(root?.left)
if lastNode == nil {
head = root
lastNode = root
} else {
//前一个节点和当前节点（root）互指，然后到下一个
root?.left = lastNode
lastNode?.right = root
lastNode = root
}
convertSubList(root?.right)
}
}
|
算法思想：在二叉搜索树中，左子结点的值总是小于父结点的值，右子节点的值总是大于父结点的值。因此我们在转换成排序双向链表时，原先指向左子结点的指针调整为链表中指向前一个结点的指针，原先指向右子节点的指针调整为链表中指向后一个结点的指针。
因为中序遍历是按照从小到大的顺序遍历二叉搜索树，所以我们用中序遍历树中的每一个节点得到的正好是要求的排好序的。遍历过程如下：
每次遍历节点的左孩子、右孩子，把左孩子指向转换链表的尾节点，并把末尾指针的右孩子指向自己。右孩子指向节点的右孩子。如果没有右孩子就返回。这一过程可以用递归实现。
github地址：https://github.com/cubegao/LeetCode
