友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
109. 有序链表转换二叉搜索树
给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为平衡 二叉搜索树。
示例 1:
输入: head = [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。
示例 2:
输入: head = [] 输出: []
提示:
-
head中的节点数在[0, 2 * 104]范围内 -
-105 <= Node.val <= 105
思路分析
这道题跟 108. 将有序数组转换为二叉搜索树 类似。可以转化成数组（或链表）进行求解。这属于空间换时间的解法。
另外一种解法，就是使用快慢指针，找到中间节点，然后再构造二叉树。
还有一种解法：利用分治+中序遍历，先逐步构建左树，然后构建根节点，最后构建右树。
-
一刷
-
二刷
-
二刷（优化）
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
/**
* Runtime: 1 ms, faster than 68.60% of Java online submissions for Convert Sorted List to Binary Search Tree.
* Memory Usage: 41.1 MB, less than 5.26% of Java online submissions for Convert Sorted List to Binary Search Tree.
*/
public TreeNode sortedListToBST(ListNode head) {
if (Objects.isNull(head)) {
return null;
}
List<Integer> nums = new ArrayList<>();
while (Objects.nonNull(head)) {
nums.add(head.val);
head = head.next;
}
return buildTree(nums, 0, nums.size());
}
private TreeNode buildTree(List<Integer> nums, int start, int end) {
if (start > end || start >= nums.size()) {
return null;
}
int mid = start + (end - start) / 2;
TreeNode root = new TreeNode(nums.get(mid));
root.left = buildTree(nums, start, mid - 1);
root.right = buildTree(nums, mid + 1, end);
return root;
}
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
/**
* 使用递归，将其逐步分解成左树，根节点，右树三部分，然后将其组成一棵树即可。
*/
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
// 这里偷懒了，也可以使用快慢指针将一个数组分解成两部分
List<Integer> nums = new ArrayList<>();
while (head != null) {
nums.add(head.val);
head = head.next;
}
return buildTree(nums, 0, nums.size() - 1);
}
private TreeNode buildTree(List<Integer> nums, int left, int right) {
if (left > right) {
return null;
}
if (left == right) {
return new TreeNode(nums.get(left));
}
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nums.get(mid));
root.left = buildTree(nums, left, mid - 1);
root.right = buildTree(nums, mid + 1, right);
return root;
}
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
ListNode globalHead = null;
/**
* 分支+中序遍历
*
* 注：没想到这个的效率更高。有点不可思议。
*
* 参考： https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/solutions/378582/you-xu-lian-biao-zhuan-huan-er-cha-sou-suo-shu-1-3/[109. 有序链表转换二叉搜索树 - 官方题解^]
*/
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
int length = getLength(head);
globalHead = head;
return buildTree(0, length - 1);
}
private TreeNode buildTree(int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode();
root.left = buildTree(left, mid - 1);
root.val = globalHead.val;
globalHead = globalHead.next;
root.right = buildTree(mid + 1, right);
return root;
}
private int getLength(ListNode head) {
int result = 0;
while (head != null) {
result++;
head = head.next;
}
return result;
}