Java 4MS Solution (BFS WITH QUEUE)


  • 0
    C
    public class Solution {
    private class bfsnode{
        TreeNode node;
        int level;
        bfsnode(TreeNode n, int l) { node = n; level = l;}
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root == null) return res;
        Queue<bfsnode> q = new LinkedList<bfsnode>();
        bfsnode b = new bfsnode(root,0);
        q.add(b);
        while(q.peek() != null){
           bfsnode cur = q.poll();
           if(cur.level == res.size()){
               List<Integer> l = new ArrayList<Integer>();
               res.add(l);
           }
           res.get(cur.level).add(cur.node.val);
           if(cur.node.left != null)
               q.add(new bfsnode(cur.node.left,cur.level+1));
           
           if(cur.node.right != null)
               q.add(new bfsnode(cur.node.right,cur.level+1));
           
         }
         return res;
    }
    }

  • 0
    T

    Consider an ArrayDeque for q it should consume less memory than links (no prev/next pointers) and add/remove is much faster (array index manipulation).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.