题目链接：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.
这道题的要求是将有序链表转化成高度平衡的二叉搜索树（BST）。
-
利用sortedArrayToBST
先将链表转化为数组，再利用Convert Sorted Array to Binary Search Tree的sortedArrayToBST函数：
由于数组有序，因此相当于二叉搜索树的前序遍历。又由于要求二叉搜索树高度平衡，即左右子树高度相差小于等于1，所以取数组中间的数作为根节点，左边作为左子树，右边作为右子树，这样就可以构造出高度平衡的二叉搜索树了。
这样，思路就和Construct Binary Tree from Preorder and Inorder Traversal以及Construct Binary Tree from Inorder and Postorder Traversal差不多，都是递归构造左右子树即可。
时间复杂度：O(n)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution
{
public:
TreeNode *sortedListToBST(ListNode *head)
{
vector<int> vi;
for(ListNode *p = head; p != NULL; p = p -> next)
vi.push_back(p -> val);
return sortedArrayToBST(vi, 0, vi.size() - 1);
}
private:
TreeNode *sortedArrayToBST(vector<int> &num, int l, int r)
{
if(l > r)
return NULL;
int m = (l + r) / 2;
TreeNode *root = new TreeNode(num[m]);
root -> left = sortedArrayToBST(num, l, m - 1);
root -> right = sortedArrayToBST(num, m + 1, r);
return root;
}
};
-
递归直接转化
上面由于需要将链表存储到数组中，这需要申请O(n)的空间，这样子不好。应该考虑直接把有序链表转化成平衡的二叉搜索树。和Convert Sorted Array to Binary Search Tree同样的思路，先找到中间的节点作为根节点，然后左边作为左子树，右边作为右子树，递归构造左右子树即可。至于如何找到中间节点，这里利用快慢指针，慢指针s每次走一步，快指针f每次走两步，这样当f到达最后节点的时候，s就指向中间节点。这样，根节点找到了，然后分别递归左边节点生成左子树，递归右边节点生成右子树。
这样，思路就和Construct Binary Tree from Preorder and Inorder Traversal以及Construct Binary Tree from Inorder and Postorder Traversal差不多，都是递归构造左右子树即可。
时间复杂度：O(nlogn)
空间复杂度：O(1)
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
class Solution
{
public:
TreeNode *sortedListToBST(ListNode *head)
{
if(head == NULL || head -> next == NULL)
return head == NULL ? NULL : new TreeNode(head -> val);
// 找到中间节点
ListNode *f = head -> next -> next, *s = head;
while(f != NULL && f -> next != NULL)
{
f = f -> next -> next;
s = s -> next;
}
ListNode *l = head, *m = s -> next, *r = m -> next;
s -> next = NULL;
TreeNode *root = new TreeNode(m -> val);
root -> left = sortedListToBST(l);
root -> right = sortedListToBST(r);
return root;
}
};
上面代码在区分左右区域的时候，使左边的最后节点指向NULL，这样处理，就改变了原始链表的结构。下面是考虑添加tail标记，使其指向要构建二叉树区域的最后节点的下一位置，这样就可以在不改变原链表结构的情况下构建二叉搜索树了。
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
class Solution
{
public:
TreeNode *sortedListToBST(ListNode *head)
{
return sortedListToBST(head, NULL);
}
private:
// 左闭右开，即head指向区间首节点，tail指向区间尾节点的next位置
TreeNode *sortedListToBST(ListNode *head, ListNode *tail)
{
if(head == tail || head -> next == tail)
return head == tail ? NULL : new TreeNode(head -> val);
// 找到中间节点
ListNode *f = head -> next -> next, *s = head;
while(f != tail && f -> next != tail)
{
f = f -> next -> next;
s = s -> next;
}
ListNode *lh = head, *lt = s -> next, *m = lt,
*rh = m -> next, *rt = tail;
TreeNode *root = new TreeNode(m -> val);
root -> left = sortedListToBST(lh, lt);
root -> right = sortedListToBST(rh, rt);
return root;
}
};
-
中序遍历
上面由于每次需要找到中心点，因此时间复杂度为O(nlogn)。然而二叉搜索树的中序遍历是有序的，因此可以用中序遍历的思路进行构造二叉搜索树，即：先构造左子树、接着构造根节点，最后构造右子树。
中序遍历时，可以只在最初找到中间节点位置，然后用l和r表示左右子树的范围。
时间复杂度：O(n)
空间复杂度：O(1)
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
class Solution
{
public:
TreeNode *sortedListToBST(ListNode *head)
{
if(head == NULL)
return NULL;
int length = 0;
for(ListNode *p = head; p != NULL; p = p -> next)
++ length;
ListNode *p = head;
return inorderTraversal(p, 0, length - 1);
}
private:
TreeNode *inorderTraversal(ListNode *&p, int l, int r)
{
if(l > r)
return NULL;
int m = l + (r - l) / 2;
TreeNode *left = inorderTraversal(p, l, m - 1);
TreeNode *root = new TreeNode(p -> val);
p = p -> next;
TreeNode *right = inorderTraversal(p, m + 1, r);
root -> left = left;
root -> right = right;
return root;
}
};