leetcode

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

min-diff-in-bst.dart (988B)

      1 //Given a tree return the minimum difference between any
      2 //two nodes in the tree. To solve I first traversed the tree and placed all
      3 //vals into a list. I could have done in order so I did not need to sort, but
      4 //really it does not speed this up much. I then did a greedy algorithm to iterate
      5 //through the sorted list to find the smallest difference in the list and returned 
      6 //that value.
      7 
      8 //Time: 306ms Beats: 100%
      9 //Memory: 148.9MB Beats: 100%
     10 
     11 class Solution {
     12     List<int> vals = [];
     13 
     14     int getMinimumDifference(TreeNode? root) {
     15         recurse(root);
     16         vals.sort();
     17         int min = 10000000;
     18         for (int i = 1; i < vals.length; ++i) {
     19             if (vals[i] - vals[i - 1] < min) {
     20                 min = vals[i] - vals[i - 1];
     21             }
     22         }
     23         return min;
     24     }
     25 
     26     void recurse(TreeNode? root) {
     27         if (root == null) {
     28             return;
     29         }
     30         vals.add(root.val);
     31         recurse(root.right);
     32         recurse(root.left);
     33     }
     34 }