Keshawn_lu's Blog

Leetcode 109. 有序链表转换二叉搜索树

字数统计: 527阅读时长: 2 min
2020/08/18 Share

题目简介:

给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

1
2
3
4
5
6
7
8
9
给定的有序链表: [-10, -3, 0, 5, 9],

一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:

0
/ \
-3 9
/ /
-10 5

思路:

由于是平衡二叉搜索树,所以我们可以每次找到链表的中位数,并以之为根节点,然后将其左边的作为左子树,右边的作为右子树,然后递归构建子树的左右子树即可。

找链表的中位数可以使用快慢指针的方法,当快指针走到头时,慢指针便走到了中点。

tips:

  • 左右区间的关系为左闭右开,因为访问后继元素较为容易(链表),并且初始化时可以使用[head, NULL)
  • 递归结束的标志是left == right,因为是左闭右开,所以此时区间内已无元素,所以返回NULL

代码如下:

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:

ListNode* getMid(ListNode* left, ListNode* right){

ListNode* slow = left;
ListNode* fast = left;

//快指针走到头,慢指针走到中点
while(fast != right && fast -> next != right){

slow = slow -> next;
fast = fast -> next -> next;
}

return slow;
}

TreeNode* CreateBST(ListNode* left, ListNode* right){

if(left == right) //区间内无元素,返回NULL
return NULL;

ListNode* mid = getMid(left, right);

TreeNode* root = new TreeNode(mid -> val);

root -> left = CreateBST(left, mid);
root -> right = CreateBST(mid -> next, right); //左闭右开

return root;
}

TreeNode* sortedListToBST(ListNode* head) {

if(head == NULL)
return NULL;

return CreateBST(head, NULL);
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: