Why is a solution based on classic bfs implementation slow? 3ms Java


  • 0
    N
    public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        
        if(root == null)
            return ret;
        
        int currDepth = 1;
        List<Integer> currLevel = new ArrayList<Integer>();
        Queue<NodeWithDepth> discovered = new LinkedList<NodeWithDepth>();
        discovered.offer(new NodeWithDepth(root, currDepth));
        
        while(true){
            NodeWithDepth n = discovered.poll();
            
            if(n == null){
                ret.add(currLevel);
                break;
            }
                
            if(n.depth != currDepth){
                //We need to put the level result to the ret, 
                //and start a new list to record curret level 
                ret.add(currLevel); 
                currLevel = new ArrayList<Integer>();
                currDepth = n.depth;
            } 
            
            currLevel.add(n.node.val);
            
            if(n.node.left != null){
                discovered.offer(new NodeWithDepth(n.node.left, n.depth + 1));
            }
            if(n.node.right != null){
                discovered.offer(new NodeWithDepth(n.node.right, n.depth + 1));
            }
        }
        
        return ret;
        
    }
    
    private class NodeWithDepth {
        TreeNode node;
        int depth;
        
        NodeWithDepth(TreeNode node, int depth){
            this.node = node;
            this.depth = depth;
        }
    }
    }

  • 0
    X

    I think the queue operations cost much time. my dfs recursive solution just needs 1ms


Log in to reply
 

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