二叉搜索树与双向链表

发表于2020-07-22更新于2020-02-22

在线测评地址：牛客网

题目描述

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

思路

1.将左子树构造成双链表，并返回链表头节点。
2.定位至左子树双链表最后一个节点。
3.如果左子树链表不为空的话，将当前root追加到左子树链表。
4.将右子树构造成双链表，并返回链表头节点。
5.如果右子树链表不为空的话，将该链表追加到root节点之后。
6.根据左子树链表是否为空确定返回的节点。

编程

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
function Convert(pRootOfTree)
{
    if (!pRootOfTree) {
        return null
    }
    if (!pRootOfTree.left && !pRootOfTree.right) {
        return pRootOfTree
    }
    var left = Convert(pRootOfTree.left)
    var p = left
    while (p && p.right) {
        p = p.right
    }
    if (left) {
        p.right = pRootOfTree
        pRootOfTree.left = p
    }
    var right = Convert(pRootOfTree.right)
    if (right) {
        right.left = pRootOfTree
        pRootOfTree.right = right
    }
    return left||pRootOfTree
    
}