Related: LeetCode 108 - Convert Sorted Array to Binary Search Tree
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/
X.
http://buttercola.blogspot.com/2014/08/leetcode-convert-sorted-list-to-binary.html
Note that in the previous solution the cost is on finding the middle node of the linked list, which takes O(n) time on average. If we can construct the tree in the order that we traverse the linked list, we don't need to jump back and forth to find the middle of the list. Remember the inorder traversal of a binary tree, if it is a BST, the inorder traversal should be in ascending order. Can we do the reverse, i.e, given an sorted list, construct the BST inorder, i.e, from bottom-up? The answer is yes.
https://leetcode.com/articles/convert-sorted-list-to-binary-search-tree/
http://www.voidcn.com/article/p-dpukkgel-brz.html
这题和Convert Sorted Array to Binary Search Tree那题看上去很像，但是从array变成了linked list，就不能O(1)寻找中间节点了。一种直接的修改就是每次遍历一半的节点来找寻中间节点。如何在不知道linked list总长的情况下遍历一半节点？双指针策略，快指针一次走2个节点，慢指针一次走1个节点，当快指针到尾部时，慢指针对应的即为中间节点。但这种方法的时间复杂度为O(N logN)：每层递归一共访问N/2个节点，一共log N层递归（对应树的高度）。
对于构建N节点的binary tree来说理论上算法复杂度最少只能到O(N)，因为生成N个节点本身就需要O(N)。要达到O(N)复杂度的算法，就不能反复遍历来查找中间节点，而只能顺序边访问linked list边构建树。这里的关键是利用构建left subtree的递归，来找寻middle节点。即构建left subtree的时候需要返回两个值：left subtree的root节点，以及整个left subtree在linked list中的下一个节点，即middle节点，也是整个left subtree的parent节点。
这个函数所做的是将*head为头的linked list构建成一个BST，然后返回BST的root，而同时，也将head移动到linked list中第end+1个节点。因为*head既是输入参数，也是返回参数，所以这里用到了指针的引用*&head。注意不能错写成了&*head。理解*&的方法是从右向左读：首先是一个引用，然后是一个对指针的引用，最后是一个对ListNode指针的引用。
http://www.cnblogs.com/springfor/p/3884031.html
https://discuss.leetcode.com/topic/8141/share-my-o-1-space-and-o-n-time-java-code
http://www.programcreek.com/2013/01/leetcode-convert-sorted-list-to-binary-search-tree-java/
X.
https://siddontang.gitbooks.io/leetcode-solution/content/tree/convert_sorted_listarray_to_binary_search_tree.html
Java Version:
Using static or class level variable.
http://joycelearning.blogspot.com/2013/09/leetcode-convert-sorted-list-to-binary.html
Using list or array.
http://rleetcode.blogspot.com/2014/02/convert-sorted-list-to-binary-search.html
http://bangbingsyb.blogspot.com/2014/11/leetcode-convert-sorted-list-to-binary.html
X. https://miafish.wordpress.com/2015/01/28/leetcode-oj-c-convert-sorted-list-to-binary-search-tree/
Solution 1: it is hard to find the mid of linked list. so convert the linked list to array and then convert array to binary search tree would be an easy way to solve this issue
X. https://leetcode.com/articles/convert-sorted-list-to-binary-search-tree/
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/
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 of every node never differ by more than 1.
Example:
Given the sorted linked list: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
http://buttercola.blogspot.com/2014/08/leetcode-convert-sorted-list-to-binary.html
Note that in the previous solution the cost is on finding the middle node of the linked list, which takes O(n) time on average. If we can construct the tree in the order that we traverse the linked list, we don't need to jump back and forth to find the middle of the list. Remember the inorder traversal of a binary tree, if it is a BST, the inorder traversal should be in ascending order. Can we do the reverse, i.e, given an sorted list, construct the BST inorder, i.e, from bottom-up? The answer is yes.
https://leetcode.com/articles/convert-sorted-list-to-binary-search-tree/
http://www.voidcn.com/article/p-dpukkgel-brz.html
- Iterate over the linked list to find out it's length. We will make use of two different pointer variables here to mark the beginning and the end of the list. Let's call them
startandendwith their initial values being0andlength - 1respectively. - Remember, we have to simulate the inorder traversal here. We can find out the middle element by using
(start + end) / 2. Note that we don't really find out the middle node of the linked list. We just have a variable telling us the index of the middle element. We simply need this to make recursive calls on the two halves. - Recurse on the left half by using
start, mid - 1as the starting and ending points. - The invariance that we maintain in this algorithm is that whenever we are done building the left half of the BST, the head pointer in the linked list will point to the root node or the middle node (which becomes the root). So, we simply use the current value pointed to by
headas the root node and progress the head node by once i.e.head = head.next - We recurse on the right hand side using
mid + 1, endas the starting and ending points.
- Time Complexity: The time complexity is still since we still have to process each of the nodes in the linked list once and form corresponding BST nodes.
- Space Complexity: since now the only extra space is used by the recursion stack and since we are building a height balanced BST, the height is bounded by .
private ListNode head;
private int findSize(ListNode head) {
ListNode ptr = head;
int c = 0;
while (ptr != null) {
ptr = ptr.next;
c += 1;
}
return c;
}
private TreeNode convertListToBST(int l, int r) {
// Invalid case
if (l > r) {
return null;
}
int mid = (l + r) / 2;
// First step of simulated inorder traversal. Recursively form
// the left half
TreeNode left = this.convertListToBST(l, mid - 1);
// Once left half is traversed, process the current node
TreeNode node = new TreeNode(this.head.val);
node.left = left;
// Maintain the invariance mentioned in the algorithm
this.head = this.head.next;
// Recurse on the right hand side and form BST out of them
node.right = this.convertListToBST(mid + 1, r);
return node;
}
public TreeNode sortedListToBST(ListNode head) {
// Get the size of the linked list first
int size = this.findSize(head);
this.head = head;
// Form the BST now that we know the size
return convertListToBST(0, size - 1);
}
https://www.geeksforgeeks.org/sorted-linked-list-to-balanced-bst/
The method 1 constructs the tree from root to leaves. In this method, we construct from leaves to root. The idea is to insert nodes in BST in the same order as the appear in Linked List, so that the tree can be constructed in O(n) time complexity. We first count the number of nodes in the given Linked List. Let the count be n. After counting nodes, we take left n/2 nodes and recursively construct the left subtree. After left subtree is constructed, we allocate memory for root and link the left subtree with root. Finally, we recursively construct the right subtree and link it with root.
While constructing the BST, we also keep moving the list head pointer to next so that we have the appropriate pointer in each recursive call.
http://bangbingsyb.blogspot.com/2014/11/leetcode-convert-sorted-list-to-binary.htmlWhile constructing the BST, we also keep moving the list head pointer to next so that we have the appropriate pointer in each recursive call.
这题和Convert Sorted Array to Binary Search Tree那题看上去很像，但是从array变成了linked list，就不能O(1)寻找中间节点了。一种直接的修改就是每次遍历一半的节点来找寻中间节点。如何在不知道linked list总长的情况下遍历一半节点？双指针策略，快指针一次走2个节点，慢指针一次走1个节点，当快指针到尾部时，慢指针对应的即为中间节点。但这种方法的时间复杂度为O(N logN)：每层递归一共访问N/2个节点，一共log N层递归（对应树的高度）。
对于构建N节点的binary tree来说理论上算法复杂度最少只能到O(N)，因为生成N个节点本身就需要O(N)。要达到O(N)复杂度的算法，就不能反复遍历来查找中间节点，而只能顺序边访问linked list边构建树。这里的关键是利用构建left subtree的递归，来找寻middle节点。即构建left subtree的时候需要返回两个值：left subtree的root节点，以及整个left subtree在linked list中的下一个节点，即middle节点，也是整个left subtree的parent节点。
这个方法非常不容易理解
TreeNode *sortedListToBST(ListNode *&head, int start, int end)
那么当left subtree构建完成后，head指向了mid，构建mid树节点。然后后移head到right subtree在linked list中的头节点。继续递归构建right subtree.
跑一个例子：
linked list: 0->1->2->NULL
call (head(0), 0, 2)
mid = 1
node(1), head(2)
/ \
call (head(0), 0, 0) call (head(2), 2, 2)
mid = 0 mid = 2
node(0), head(1) node(2), head(NULL)
/ \ / \
call (head(0), 0, -1) call (head(0), 1, 0) call (head(2), 2, 1) call (head(0), 2, 1)
return NULL return NULL return NULL return NULL
最终结果：
1
/ \
0 2
TreeNode *sortedListToBST(ListNode *head) { int listLen = 0; ListNode *cur = head; while(cur) { listLen++; cur = cur->next; } return sortedListToBST(head, 0, listLen-1); } TreeNode *sortedListToBST(ListNode *&head, int start, int end) { if(start>end) return NULL; int mid = start + (end-start)/2; TreeNode *leftChild = sortedListToBST(head, start, mid-1); TreeNode *root = new TreeNode(head->val); head = head->next; TreeNode *rightChild = sortedListToBST(head, mid+1, end); root->left = leftChild; root->right = rightChild; return root; }http://www.jiuzhang.com/solutions/convert-sorted-list-to-binary-search-tree/
http://www.cnblogs.com/springfor/p/3884031.html
之前做过一道是从sorted array转换到BinarySearchTree的，方法还是一样二分法。但是构造树的方法不是由顶至下了，是要由低至上的建立。
build from bottom up instead of up bottom would reduce the time from O(nlgn) to O(n)https://discuss.leetcode.com/topic/8141/share-my-o-1-space-and-o-n-time-java-code
http://www.programcreek.com/2013/01/leetcode-convert-sorted-list-to-binary-search-tree-java/
Here is similar solution where list state is stored in a parameter instead of a field which I believe makes it a thread safe implementation:
private static class State {
ListNode head;
State(ListNode head) {
this.head = head;
}
}
public TreeNode sortedListToBST(ListNode head) {
return sortedListToBST(size(head), new State(head));
}
private TreeNode sortedListToBST(int size, State state) {
if (size<=0) return null;
int mid = size/2;
TreeNode root = new TreeNode(0);
root.left = sortedListToBST(mid, state);
root.val = state.head.val;
state.head = state.head.next;
root.right = sortedListToBST(size - mid - 1, state);
return root;
}
private int size(ListNode head) {
int size = 0;
while (head != null) {
head = head.next;
size++;
}
return size;
}private ListNode node;
public TreeNode sortedListToBST(ListNode head) {
if(head == null){
return null;
}
int size = 0;
ListNode runner = head;
node = head;
while(runner != null){
runner = runner.next;
size ++;
}
return inorderHelper(0, size - 1);
}
public TreeNode inorderHelper(int start, int end){
if(start > end){
return null;
}
int mid = start + (end - start) / 2;
TreeNode left = inorderHelper(start, mid - 1);
TreeNode treenode = new TreeNode(node.val);
treenode.left = left;
node = node.next;
TreeNode right = inorderHelper(mid + 1, end);
treenode.right = right;
return treenode;
}X.
https://siddontang.gitbooks.io/leetcode-solution/content/tree/convert_sorted_listarray_to_binary_search_tree.html
这题的难点在于如何找到链表的中间节点，我们可以通过fast，slow指针来解决，fast每次走两步，slow每次走一步，fast走到结尾，那么slow就是中间节点了。
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/35476/Share-my-JAVA-solution-1ms-very-short-and-concisepublic TreeNode sortedListToBST(ListNode head) {
if(head==null) return null;
return toBST(head,null);
}
public TreeNode toBST(ListNode head, ListNode tail){
ListNode slow = head;
ListNode fast = head;
if(head==tail) return null;
while(fast!=tail&&fast.next!=tail){
fast = fast.next.next;
slow = slow.next;
}
TreeNode thead = new TreeNode(slow.val);
thead.left = toBST(head,slow);
thead.right = toBST(slow.next,tail);
return thead;
}public TreeNode sortedListToBST(ListNode head) { if (head == null) return null; ListNode fast = head, slow = head, pre = head; while (fast != null && fast.next != null) { pre = slow; fast = fast.next.next; slow = slow.next; } pre.next = null; TreeNode root = new TreeNode(slow.val); root.left = (head != slow) ? sortedListToBST(head) : null; root.right = sortedListToBST(slow.next); return root; }
The method 1 constructs the tree from root to leaves. In this method, we construct from leaves to root. The idea is to insert nodes in BST in the same order as the appear in Linked List, so that the tree can be constructed in O(n) time complexity. We first count the number of nodes in the given Linked List. Let the count be n. After counting nodes, we take left n/2 nodes and recursively construct the left subtree. After left subtree is constructed, we allocate memory for root and link the left subtree with root. Finally, we recursively construct the right subtree and link it with root.
While constructing the BST, we also keep moving the list head pointer to next so that we have the appropriate pointer in each recursive call.
While constructing the BST, we also keep moving the list head pointer to next so that we have the appropriate pointer in each recursive call.
/* head node of link list */ LNode head; /* This function counts the number of nodes in Linked List and then calls sortedListToBSTRecur() to construct BST */ TNode sortedListToBST() { /*Count the number of nodes in Linked List */ int n = countNodes(head); /* Construct BST */ return sortedListToBSTRecur(n); } /* The main function that constructs balanced BST and returns root of it. n --> No. of nodes in the Doubly Linked List */ TNode sortedListToBSTRecur(int n) { /* Base Case */ if (n <= 0) return null; /* Recursively construct the left subtree */ TNode left = sortedListToBSTRecur(n / 2); /* head_ref now refers to middle node, make middle node as root of BST*/ TNode root = new TNode(head.data); // Set pointer to left subtree root.left = left; /* Change head pointer of Linked List for parent recursive calls */ head = head.next; /* Recursively construct the right subtree and link it with root. The number of nodes in right subtree is total nodes - nodes in left subtree - 1 (for root) */ root.right = sortedListToBSTRecur(n - n / 2 - 1); return root; }
We create nodes bottom-up, and assign them to its parents. The bottom-up approach enables us to access the list in its order while creating nodes.
Isn’t the bottom-up approach neat? Each time you are stucked with the top-down approach, give bottom-up a try. Although bottom-up approach is not the most natural way we think, it is extremely helpful in some cases. However, you should prefer top-down instead of bottom-up in general, since the latter is more difficult to verify in correctness.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
if (start > end) return NULL;
// same as (start+end)/2, avoids overflow
int mid = start + (end - start) / 2;
BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
BinaryTree *parent = new BinaryTree(list->data);
parent->left = leftChild;
list = list->next;
parent->right = sortedListToBST(list, mid+1, end);
return parent;
}
BinaryTree* sortedListToBST(ListNode *head, int n) {
return sortedListToBST(head, 0, n-1);
}
|
Using static or class level variable.
http://joycelearning.blogspot.com/2013/09/leetcode-convert-sorted-list-to-binary.html
static ListNode head; public TreeNode sortedListToBST(ListNode head) { if(head == null) return null; this.head = head; // get list length int len = 0; ListNode ln = head; while(ln != null){ len++; ln = ln.next; } return sortedListToBST(0, len - 1); } // build bottom-to-top public TreeNode sortedListToBST(int start, int end) { // if finished (root) if(start > end) return null; // get mid val int mid = (start + end) / 2; // build left sub tree TreeNode left = sortedListToBST(start, mid - 1); // build root node TreeNode root = new TreeNode(head.val); root.left = left; // move to next node to build right sub tree head = head.next; root.right = sortedListToBST(mid + 1, end); return root; }http://rleetcode.blogspot.com/2014/02/convert-sorted-list-to-binary-search.html
https://gyaneshwarpardhi.wordpress.com/2014/06/14/construct-balanced-binary-search-tree-using-sorted-array/public TreeNode sortedListToBST(ListNode head) {if (head==null) {return null;}ListNode temp=head;int start=0;int end=0;while (temp.next!=null){temp=temp.next;end++;}// java is pass by value, so inorder to memory the move of the head// you have to put the head into a array or other warpper classListNode[] headHolder={head};return buildTree(headHolder,start, end );}private TreeNode buildTree(ListNode[] headHolder, int start, int end){if (start>end){return null;}int mid=(start+end)/2;TreeNode left=buildTree(headHolder, start, mid-1);TreeNode root=new TreeNode (headHolder[0].val);// current node in ListNode has been used, move it one step to the rightheadHolder[0]=headHolder[0].next;root.left=left;TreeNode right=buildTree (headHolder, mid+1, end);root.right=right;return root;}
treeNode* sortedArrayToBinrySearchTree(int a[], int left, int right) { int mid; if (left > right) return NULL; mid = (left + right) / 2; treeNode *temp = new treeNode(a[mid]); temp->leftChild = sortedArrayToBinrySearchTree(a, left, mid - 1); temp->rightChild = sortedArrayToBinrySearchTree(a, mid + 1, right); return temp;}http://bangbingsyb.blogspot.com/2014/11/leetcode-convert-sorted-list-to-binary.html
这个函数所做的是将*head为头的linked list构建成一个BST，然后返回BST的root，而同时，也将head移动到linked list中第end+1个节点。因为*head既是输入参数，也是返回参数，所以这里用到了指针的引用*&head。注意不能错写成了&*head。理解*&的方法是从右向左读：首先是一个引用，然后是一个对指针的引用，最后是一个对ListNode指针的引用。
那么当left subtree构建完成后，head指向了mid，构建mid树节点。然后后移head到right subtree在linked list中的头节点。继续递归构建right subtree.
O(nlogn)
private TreeNode helper(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return new TreeNode(head.val);
}
ListNode pre = null;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
pre.next = null;
TreeNode root = new TreeNode(slow.val);
TreeNode L = helper(head);
TreeNode R = helper(slow.next);
root.left = L;
root.right = R;
return root;
} Solution 1: it is hard to find the mid of linked list. so convert the linked list to array and then convert array to binary search tree would be an easy way to solve this issue
public TreeNode SortedListToBST(ListNode head)
{
var values = new List();
while (head != null)
{
values.Add(head.val);
head = head.next;
}
return SortedArrayToBST(values.ToArray(), 0, values.Count - 1);
}
private TreeNode SortedArrayToBST(int[] values, int low, int high)
{
if (low > high)
{
return null;
}
var mid = (high - low)/2 + low;
var root = new TreeNode(values[mid])
{
left = SortedArrayToBST(values, low, mid - 1),
right = SortedArrayToBST(values, mid + 1, high)
};
return root;
}
X. https://leetcode.com/articles/convert-sorted-list-to-binary-search-tree/- Time Complexity: The time complexity comes down to just now since we convert the linked list to an array initially and then we convert the array into a BST. Accessing the middle element now takes time and hence the time complexity comes down.
- Space Complexity: Since we used extra space to bring down the time complexity, the space complexity now goes up to as opposed to just in the previous solution. This is due to the array we construct initially.
private List<Integer> values;
public Solution() {
this.values = new ArrayList<Integer>();
}
private void mapListToValues(ListNode head) {
while (head != null) {
this.values.add(head.val);
head = head.next;
}
}
private TreeNode convertListToBST(int left, int right) {
// Invalid case
if (left > right) {
return null;
}
// Middle element forms the root.
int mid = (left + right) / 2;
TreeNode node = new TreeNode(this.values.get(mid));
// Base case for when there is only one element left in the array
if (left == right) {
return node;
}
// Recursively form BST on the two halves
node.left = convertListToBST(left, mid - 1);
node.right = convertListToBST(mid + 1, right);
return node;
}
public TreeNode sortedListToBST(ListNode head) {
// Form an array out of the given linked list and then
// use the array to form the BST.
this.mapListToValues(head);
// Convert the array to
return convertListToBST(0, this.values.size() - 1);
}
X. https://leetcode.com/articles/convert-sorted-list-to-binary-search-tree/
- Once we have the middle element of the linked list, we disconnect the portion of the list to the left of the middle element. The way we do this is by keeping a
prev_ptras well which points to one node before theslow_ptri.e.prev_ptr.next=slow_ptr. For disconnecting the left portion we simply doprev_ptr.next = None - We only need to pass the head of the linked list to the function that converts it to a height balances BST. So, we recurse on the left half of the linked list by passing the original head of the list and on the right half by passing
slow_ptr.nextas the head.
- Time Complexity: . Suppose our linked list consists of elements. For every list we pass to our recursive function, we have to calculate the middle element for that list. For a list of size , it takes steps to find the middle element i.e. to find the mid. We do this for every half of the original linked list. From the looks of it, this seems to be an algorithm. However, on closer analysis, it turns out to be a bit more efficient than .Let's look at the number of operations that we have to perform on each of the halves of the linked list. As we mentioned earlier, it takes steps to find the middle of a linked list with elements. After finding the middle element, we are left with two halves of size each. Then, we find the middle element for
bothof these halves and it would take a total of steps for that. And similarly for the smaller sublists that keep forming recursively. This would give us the following series of operations for a list of size .
Essentially, this is done times since we split the linked list in half every time. Hence, the above equation becomes: - Space Complexity: O(logN). Since we are resorting to recursion, there is always the added space complexity of the recursion stack that comes into picture. This could have been for a skewed tree, but the question clearly states that we need to maintain the height balanced property. This ensures the height of the tree to be bounded by . Hence, the space complexity is .
The main problem with the above solution seems to be the middle element computation. That takes up a lot of unnecessary time and this is due to the nature of the linked list data structure. Let's look at the next solution which tries to overcome this.
For those who can't calculate time complexity in solution 1 using forward iteration (guess) or formal calculation(using recursion method and then conclude, like author does).
You could use master theorem to solve this kind of conquer and divide problem's complexity. Although this's simple to CS student, but it's actually my first time try to use master theorem to analyze problem other than homework.
We divide the origin problem into two subproblem with size of n/2 recursively, and do find-mid operation, which takes n/2 steps before recursively solving two subproblem. So our complexity could write as
There are 3 usage case of master theorem:
case 1:
case 2:
case 3:
Here we just use case 2. According to the theorem, we have
You could use master theorem to solve this kind of conquer and divide problem's complexity. Although this's simple to CS student, but it's actually my first time try to use master theorem to analyze problem other than homework.
We divide the origin problem into two subproblem with size of n/2 recursively, and do find-mid operation, which takes n/2 steps before recursively solving two subproblem. So our complexity could write as
T(n) = 2*T(n/2) + n/2 just like many other conquer and divide problem does. More general, T(n) = a*T(n/b)+ f(n), which divide a problem into a subproblem of size(n/b) and f(n) is extra cost for operation like preprocessing in this case or merging subproblem result like merge sort.There are 3 usage case of master theorem:
case 1:
f(n) is belongs to Big O of n^(logb(a)- e)for some e > 0=> T(n) belongs to Big theta n^logb(a)case 2:
f(n) is belongs to Big theta of n^(logb(a)) => T(n) belongs to Big theta n^logb(a)*lgncase 3:
f(n) is belongs to Big omega of n^(logb(a)- e)for some e > 0 , with some regularity condition => T(n) belongs to Big theta f(n)Here we just use case 2. According to the theorem, we have
T(n) belongs to Big theta n^logb(a)*lgn. Sinceb = 2,a = 2, f(n) = n/2, we got Big theta ofn*lgn .
Sorry for the poor edit, dont know how to insert belong to math symbol in markdown. Also for the regularity condition, please refer to master theorem wikipedia.
https://leetcode.com/articles/convert-sorted-list-to-binary-search-tree/
private ListNode findMiddleElement(ListNode head) {
// The pointer used to disconnect the left half from the mid node.
ListNode prevPtr = null;
ListNode slowPtr = head;
ListNode fastPtr = head;
// Iterate until fastPr doesn't reach the end of the linked list.
while (fastPtr != null && fastPtr.next != null) {
prevPtr = slowPtr;
slowPtr = slowPtr.next;
fastPtr = fastPtr.next.next;
}
// Handling the case when slowPtr was equal to head.
if (prevPtr != null) {
prevPtr.next = null;
}
return slowPtr;
}
public TreeNode sortedListToBST(ListNode head) {
// If the head doesn't exist, then the linked list is empty
if (head == null) {
return null;
}
// Find the middle element for the list.
ListNode mid = this.findMiddleElement(head);
// The mid becomes the root of the BST.
TreeNode node = new TreeNode(mid.val);
// Base case when there is just one element in the linked list
if (head == mid) {
return node;
}
// Recursively form balanced BSTs using the left and right halves of the
// original list.
node.left = this.sortedListToBST(head);
node.right = this.sortedListToBST(mid.next);
return node;
}
Read full article from Convert Sorted List to Balanced Binary Search Tree (BST) | LeetCode