-
Notifications
You must be signed in to change notification settings - Fork 0
/
Convert Sorted List to Binary Search Tree.cpp
157 lines (141 loc) · 4.11 KB
/
Convert Sorted List to Binary Search Tree.cpp
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
///@file Convert Sorted List to Binary Search Tree
// Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
///@author zhaowei
///@date 2015.07.23
///@version 1.0
///@date 2015.08.24
///@version 2.0
///@date 2016.01.05
///@version 2.1
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution_v1 {
public:
///@brief 将已经排好序的链表转换成高度平衡的BST树
///@param head 链表表头
///@return 返回构造的高度平衡二叉搜索树的根节点
/* @note 与"Convert Sorted Array to Binary Search Tree"类似,也是找链表中的中位数作为当前节点,其前半部分是左子树,右半部分是右子树。递归
构造即可。时间复杂度为O(n),空间复杂度为O(1)*/
TreeNode* sortedListToBST(ListNode* head) {
int len = 0;
ListNode *indx = head;
while(indx != nullptr)
{
indx = indx->next;
len++;
}
return sortedListToBST_Recur(head, len);
}
private:
///@brief 递归构造高度平衡二叉搜索树
///@param head 链表表头
///@param len 待处理的链表长度
///@return 返回构造的高度平衡二叉搜索树的根节点
TreeNode* sortedListToBST_Recur(ListNode *head, int len)
{
if (len == 0) return nullptr;
int mid = len / 2; // 中位数下标
ListNode *indx = head;
while (mid != 0)
{
indx = indx->next;
mid--;
}
TreeNode *root = new TreeNode(indx->val);
root->left = sortedListToBST_Recur(head, len/2); // 因为int整型除法只保留整数部分,故当len为偶数时,中位数为后半部分的第一个,左半部分就是整个长度的一半。
root->right = sortedListToBST_Recur(indx->next, (len-1)/2);
return root;
}
};
class Solution_v2 {
public:
TreeNode* sortedListToBST(ListNode* head) {
int len = 0;
ListNode* indx = head;
while (indx)
{
indx = indx->next;
len++;
}
return convert(head, len);
}
private:
TreeNode* convert(ListNode* head, int len)
{
if (!len) return nullptr;
int m = len / 2;
ListNode* mid = head;
while (m--)
mid = mid->next;
TreeNode* root = new TreeNode(mid->val);
root->left = convert(head, len/2);
root->right = convert(mid->next, (len-1)/2);
return root;
}
};
class Solution {
public:
///@brief 将已经排好序的链表转换成高度平衡的BST树
///@param head 链表表头
///@return 返回构造的高度平衡二叉搜索树的根节点
///@note 1. 递归;2. 与有序数组转换BST类似,也是需要找到当前链表的中位值来作为当前节点;
// 3. 因为int型变量的除法是向下取整,故左子树长度为len - 1,这样不论len为奇偶都可以处理。而右子树需要除去当前子树根节点,所以应为(len - 1) / 2。
TreeNode* sortedListToBST(ListNode* head) {
if (!head) return nullptr;
int len = 0;
ListNode* indx = head;
while (indx) {
len++;
indx = indx->next;
}
return helper(head, len);
}
///@brief 递归辅助函数
///@param head 链表表头
///@param len 链表长度
///@return 返回当前链表组成的子树根节点
TreeNode* helper(ListNode* head, int len) {
if (!len || !head) return nullptr;
int mid = len / 2;
ListNode* indx = head;
while (mid) {
indx = indx->next;
mid--;
}
TreeNode* root = new TreeNode(indx->val);
root->left = helper(head, len / 2); // 因为int型变量的除法是向下取整,故左子树长度为len - 1,这样不论len为奇偶都可以处理
root->right = helper(indx->next, (len - 1) / 2); // 而右子树需要除去当前子树根节点,所以应为(len - 1) / 2
return root;
}
};
int main()
{
ListNode* head = new ListNode(0);
ListNode* ln[6];
for (int i = 0; i != 6; i++)
{
ln[i] = new ListNode(i+1);
}
for (int i = 0; i != 5; i++)
{
ln[i]->next = ln[i+1];
}
head = ln[0];
head->next->next = nullptr;
head->next->val = 3;
Solution slt;
TreeNode *root = slt.sortedListToBST(head);
return 0;
}