leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

convert-sorted-list-to-binary-search-tree.dart (1155B)

      1 //Convert the given linked list to a height-balanced
      2 //binary tree. To do this I converted the linked list to an array
      3 //then converted the array to a binary search tree. The time complexity
      4 //of this is O(nlog(n)). 
      5 //Time: 289ms Beats: 77.78%
      6 //Memory: 147.5MB Beats: 5.56%
      7 
      8 /**
      9  * Definition for singly-linked list.
     10  * class ListNode {
     11  *   int val;
     12  *   ListNode? next;
     13  *   ListNode([this.val = 0, this.next]);
     14  * }
     15  */
     16 /**
     17  * Definition for a binary tree node.
     18  * class TreeNode {
     19  *   int val;
     20  *   TreeNode? left;
     21  *   TreeNode? right;
     22  *   TreeNode([this.val = 0, this.left, this.right]);
     23  * }
     24  */
     25 class Solution {
     26   TreeNode? sortedListToBST(ListNode? head) {
     27     List<int> vals = [];
     28     while(head != null){
     29       vals.add(head.val);
     30       head = head.next;
     31     }
     32     TreeNode? return_tree = createBST(vals);
     33     return return_tree;
     34   }
     35 
     36   TreeNode? createBST(nums){
     37     if(nums.isEmpty){
     38       return null;
     39     }
     40     int mid = (nums.length / 2).toInt();
     41     TreeNode root = new TreeNode();
     42     root.val = nums[mid];
     43     root.left = createBST(nums.sublist(0 , mid));
     44     root.right = createBST(nums.sublist(mid + 1));
     45     return root;
     46   }
     47 
     48 
     49 }