二叉搜索树与双向链表

发表于 更新于

描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

注意:

  1. 要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
  2. 返回链表中的第一个节点的指针
  3. 函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

输入描述：
二叉树的根节点

返回值描述：
双向链表的其中一个头节点。

题解

已知将二叉搜索树进行中序遍历可以得到由小到大的顺序排列，因此最直接的想法就是进行中序遍历。将中序遍历的结果用数组存储下来，得到的数组是有从小到大顺序的。最后将数组中的结点依次连接即可

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
package main

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

/**
 * 
 * @param pRootOfTree TreeNode类 
 * @return TreeNode类
*/
func Convert( pRootOfTree *TreeNode ) *TreeNode {
    // write code here
    if pRootOfTree == nil {
        return nil
    }
    nodes := []*TreeNode{}
    inorder(&nodes, pRootOfTree)

    head := &TreeNode{Val: nodes[0].Val}

    preHead := head

    for index := 1; index < len(nodes); index++ {
        head.Right = nodes[index]
        nodes[index].Left = head
        head = head.Right
    }

    return preHead
}

func inorder(nodes *[]*TreeNode, root *TreeNode) {
    if root == nil {
        return
    }

    inorder(nodes, root.Left)
    *nodes = append(*nodes, root)
    inorder(nodes, root.Right)
}