leetcode

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

binary-tree-level-order-traversal-ii.dart (1322B)

      1 //Given a binary tree traverse it layer by layer (BFS)
      2 //and return the reverse order of the layers meaning from
      3 //bottom to top left to right.
      4 //The time complexity of this code is O(n) where n is the length
      5 //of the linked list. The only way to optimize this would be to
      6 //use some form of constant time queue as opposed to using sublist
      7 //which takes O(n) time each time.
      8 //Time: 246ms Beats: 100%
      9 //Memory: 142.5MB Beats: 100%
     10 class Solution {
     11   List<List<int>> levelOrderBottom(TreeNode? root) {
     12       if(root == null){
     13           return [];
     14       }
     15       List<TreeNode?> queue = [];        
     16       queue.add(root);
     17       List<List<int>> forward_order = [];
     18       while(queue.length > 0){
     19           int init_length = queue.length;
     20           for(int i = 0 ; i < init_length ; ++i){
     21               TreeNode? current = queue[i];
     22               if(current?.left != null){
     23                   queue.add(current?.left);
     24               }
     25               if(current?.right != null){
     26                   queue.add(current?.right);
     27               }
     28           }
     29           List<int> subl = [];
     30           for(int i = 0 ; i < init_length ; ++i){
     31             subl.add(queue[i]?.val ?? 0);
     32           }
     33           forward_order.add(subl);
     34           queue = queue.sublist(init_length);
     35       }
     36       return forward_order.reversed.toList();
     37     }
     38 }