leetcode

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

validate-binary-search-tree.dart (1078B)

      1 //Return true if the binary search tree is valid and false
      2 //if it is not.
      3 //To tell if it is valid verify that the left node is always
      4 //less than the root node, and the right node is always greater than
      5 //the root node.
      6 //My solution uses an inorder search of the tree to first get a list
      7 //of the nodes in order. Then, I go through the list checking if they are 
      8 //actually in order and if they are not return false.
      9 //The time complexity of this code is O(n) where n is the number
     10 //of nodes in the list.
     11 //Time: 294MB Beats: 40.91%
     12 //Memory: 146.6MB Beats: 15.91%
     13 class Solution {
     14   List<int> order_vals = [];
     15   bool isValidBST(TreeNode? root) {
     16       recurse(root);
     17       int last = order_vals[0];
     18       for(int i = 1 ; i < order_vals.length ; ++i){
     19           if(order_vals[i] <= last){
     20               return false;
     21           }
     22           last = order_vals[i];
     23       }
     24       return true;
     25 
     26   }
     27   void recurse(TreeNode? root){
     28       if(root == null){
     29           return;
     30       }
     31       recurse(root.left);
     32       order_vals.add((root?.val ?? 0));
     33       recurse(root.right);
     34   }
     35 }