109 Convert Sorted List to Binary Search Tree

Search…

109. Convert Sorted List to Binary Search Tree​
1. Question
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees ofeverynode never differ by more than 1.
Example:
1
Given the sorted linked list: [-10,-3,0,5,9],
2
​
3
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
4
​
5
      0
6
     / \
7
   -3   9
8
   /   /
9
 -10  5
Copied!
2. Implementation
(1) Recursion
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode(int x) { val = x; }
7
 * }
8
 */
9
/**
10
 * Definition for a binary tree node.
11
 * public class TreeNode {
12
 *     int val;
13
 *     TreeNode left;
14
 *     TreeNode right;
15
 *     TreeNode(int x) { val = x; }
16
 * }
17
 */
18
class Solution {
19
    public TreeNode sortedListToBST(ListNode head) {
20
        return convertToBST(head, null);
21
    }
22
​
23
    public TreeNode convertToBST(ListNode start, ListNode end) {
24
        if (start == null || start == end) {
25
            return null;
26
        }
27
​
28
        ListNode fast = start;
29
        ListNode slow = start;
30
​
31
        while (fast.next != end && fast.next.next != end) {
32
            fast = fast.next.next;
33
            slow = slow.next;
34
        }
35
​
36
        TreeNode root = new TreeNode(slow.val);
37
        root.left = convertToBST(start, slow);
38
        root.right = convertToBST(slow.next, end);
39
        return root;
40
    }
41
}
Copied!
3. Time & Space Complexity
Recursion: 时间复杂度O(nlogn), 空间复杂度O(logn)

92 Reverse Linked List II

141 Linked List Cycle

Last modified 2yr ago

Copy link

Contents

109. Convert Sorted List to Binary Search Tree

1. Question

2. Implementation

3. Time & Space Complexity

109. Convert Sorted List to Binary Search Tree​

1. Question

2. Implementation

3. Time & Space Complexity

109. Convert Sorted List to Binary Search Tree