二叉搜索树转双向链表

题目描述

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

解题思路

题目可能比较难理解,可以看如下的图,我们有一棵二叉搜索树,要求得右边的双向链表。

BST

在二叉搜索树中,左子结点的值总是小于父结点的值,右子节点的值总是大于父结点的值。因此我们在转换成排序双向链表时,原先指向左子结点的指针调整为链表中指向前一个结点的指针,原先指向右子节点的指针调整为链表中指向后一个结点的指针。由于要求链表是有序的,可以借助二叉树中序遍历,因为中序遍历算法的特点就是从小到大访问结点。当遍历访问到根结点时,假设根结点的左侧已经处理好,只需将根结点与上次访问的最近结点(左子树中最大值结点)的指针连接好即可。进而更新当前链表的最后一个结点指针。同时中序遍历过程正好是转换成链表的过程,可采用递归方法处理。

代码实现

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
/**
* 双向链表节点
*/
class DLNode {
public $data;
public $next; // 指向下一个节点
public $prev; // 指向前一个节点

public function __construct($data) {
$this->data = $data;
$this->next = null;
$this->prev = null;
}
}

class DoubleLinkedList {
private $head;

public function append($data) {
$node = new DLNode($data);
if ($this->head == null) {
$this->head = $node;
} else {
$this->appendNode($this->head, $node);
}
}

private function appendNode($node, $newNode) {
if ($node->next == null) {
$node->next = $newNode;
$newNode->prev = $node;
} else {
$this->appendNode($node->next, $newNode);
}
}

public function toString() {
$str = $this->head->data;
$current = $this->head->next;

while ($current) {
$str .= ','.$current->data;
$current = $current->next;
}

return $str;
}
}

/**
* 将二叉搜索树转换成一个排序的双向链表
*/
public function convertDLinked() {
$dlink = new DoubleLinkedList();
$this->convertDLinkedNode($this->root, $dlink);
return $dlink;
}

private function convertDLinkedNode($node, $dlink) {
if ($node != null) {
$this->convertDLinkedNode($node->left, $dlink);
$dlink->append($node->data);
$this->convertDLinkedNode($node->right, $dlink);
}
}
有用就打赏一下作者吧!