-
Notifications
You must be signed in to change notification settings - Fork 17
/
convert_binary_search_tree.php
83 lines (76 loc) · 2.45 KB
/
convert_binary_search_tree.php
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
<?php
/**
* 剑指 Offer 系列:将二叉搜索树转化为排序的双向链表
* Author:学院君
*/
require_once './binary_tree_node.php';
function Convert(BinaryTreeNode $root): BinaryTreeNode
{
// $lastNodeInList 指向双向链表的尾结点,也是二叉树最大值对应结点
$lastNodeInList = null;
// 调用 ConverNode 递归处理结点转化,从二叉树根结点开始
ConvertNode($root, $lastNodeInList);
// $lastNodeInList 指向双向链表的尾结点,最后我们需要返回头结点
$headOfList = $lastNodeInList;
// 头结点的设置方式:从尾结点依次往左遍历,直到某个结点前驱结点不存在,将其返回作为头结点
while ($headOfList != null && $headOfList->left != null) {
$headOfList = $headOfList->left;
}
return $headOfList;
}
// 通过中序遍历二叉搜索树将二叉树结点转化为链表结点
function ConvertNode(BinaryTreeNode $node = null, BinaryTreeNode &$lastNodeInList = null)
{
if ($node == null) {
return;
}
$current = $node;
// 递归处理左子树
if ($current->left != null) {
ConvertNode($current->left, $lastNodeInList);
}
// 转化逻辑核心实现:
// 1、将当前结点的前驱结点指向上一次处理后的尾结点
// 2、如果尾结点不为空,则将其后驱结点指向当前结点
// 3、最后将为当前结点设置为本次处理后的尾结点
$current->left = $lastNodeInList;
if ($lastNodeInList != null) {
$lastNodeInList->right = $current;
}
$lastNodeInList = $current;
// 递归处理右子树
if ($current->right != null) {
ConvertNode($current->right, $lastNodeInList);
}
}
// 测试代码
$root = new BinaryTreeNode();
$root->data = 10;
$left = new BinaryTreeNode();
$left->data = 6;
$right = new BinaryTreeNode();
$right->data = 14;
$left_1 = new BinaryTreeNode();
$left_1->data = 4;
$left_2 = new BinaryTreeNode();
$left_2->data = 8;
$right_1 = new BinaryTreeNode();
$right_1->data = 12;
$right_2 = new BinaryTreeNode();
$right_2->data = 16;
$root->left = $left;
$root->right = $right;
$left->left = $left_1;
$left->right = $left_2;
$right->left = $right_1;
$right->right = $right_2;
$headOfList = Convert($root);
if ($headOfList != null) {
$node = $headOfList;
while ($node != null) {
printf("%d ", $node->data);
$node = $node->right;
}
echo "\n";
}
// 打印结果是 4 6 8 10 12 14 16