1. 题目描述

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

2. 思路分析

在搜索二叉树中，左子结点的值总是小于父结点的值，右子结点的值总是大于父结点的值。因此我们在转换成排序双向链表时，原先指向左子结点的指针调整为链表中指向前一个结点的指针，原先指向右子结点的指针调整为链表中指向后一个结点指针。

因为要遍历树，所以要选取遍历算法。为了保证遍历的有序性，采用中序遍历。在 convertNode 函数实现中，注意 lastNodeInList 语意，剩下的按照思路写出来即可。

3. 代码实现

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
class TreeNode {
    constructor(value, left = null, right = null) {
        this.value = value
        this.left = left
        this.right = right
    }
}

/**
 * 将node和左右子树转化为双向链表
 * @param {TreeNode} node 待转化的节点
 * @param {TreeNode} lastNodeInList 已转换好的双向链表的尾结点
 */
function convertNode(node, lastNodeInList = null) {
    if (!node) {
        return null
    }

    // 先处理左子树
    if (node.left) {
        lastNodeInList = convertNode(node.left, lastNodeInList)
    }

    // 将当前节点与原双向链表拼接
    node.left = lastNodeInList
    if (lastNodeInList) {
        lastNodeInList.right = node
    }

    // 处理右子树
    lastNodeInList = node
    if (node.right) {
        lastNodeInList = convertNode(node.right, lastNodeInList)
    }

    // 返回新链表的尾节点
    return lastNodeInList
}

/**
 *
 * @param {TreeNode} root
 */
function convertTreeToList(root) {
    let lastNodeInList = convertNode(root)
    let headOfList = lastNodeInList
    // 返回转化好的双向链表的头节点
    while (headOfList && headOfList.left) {
        headOfList = headOfList.left
    }
    return headOfList
}

/**
 * 测试代码
 */

const root = new TreeNode(10, new TreeNode(6, new TreeNode(4), new TreeNode(8)), new TreeNode(14, new TreeNode(12), new TreeNode(16)))

let nodeOfList = convertTreeToList(root)
while (nodeOfList) {
    console.log(nodeOfList.value)
    nodeOfList = nodeOfList.right
}