leetcode

commit dc5c58999def219583f9b3facc856b4c68ddf375
parent 2b8100e7a0ee9cc3eb85bb6b274641ecba279a31
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Thu,  4 May 2023 13:55:25 -0500

Completed ocnvert sorted list to binary search tree

Diffstat:
A
convert-sorted-list-to-binary-search/convert-sorted-list-to-binary-search-tree.dart
 | 
49
+++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 49 insertions(+), 0 deletions(-)
diff --git a/convert-sorted-list-to-binary-search/convert-sorted-list-to-binary-search-tree.dart b/convert-sorted-list-to-binary-search/convert-sorted-list-to-binary-search-tree.dart
@@ -0,0 +1,49 @@
+//Convert the given linked list to a height-balanced
+//binary tree. To do this I converted the linked list to an array
+//then converted the array to a binary search tree. The time complexity
+//of this is O(nlog(n)). 
+//Time: 289ms Beats: 77.78%
+//Memory: 147.5MB Beats: 5.56%
+
+/**
+ * Definition for singly-linked list.
+ * class ListNode {
+ *   int val;
+ *   ListNode? next;
+ *   ListNode([this.val = 0, this.next]);
+ * }
+ */
+/**
+ * Definition for a binary tree node.
+ * class TreeNode {
+ *   int val;
+ *   TreeNode? left;
+ *   TreeNode? right;
+ *   TreeNode([this.val = 0, this.left, this.right]);
+ * }
+ */
+class Solution {
+  TreeNode? sortedListToBST(ListNode? head) {
+    List<int> vals = [];
+    while(head != null){
+      vals.add(head.val);
+      head = head.next;
+    }
+    TreeNode? return_tree = createBST(vals);
+    return return_tree;
+  }
+
+  TreeNode? createBST(nums){
+    if(nums.isEmpty){
+      return null;
+    }
+    int mid = (nums.length / 2).toInt();
+    TreeNode root = new TreeNode();
+    root.val = nums[mid];
+    root.left = createBST(nums.sublist(0 , mid));
+    root.right = createBST(nums.sublist(mid + 1));
+    return root;
+  }
+
+
+}