Java BFS - Deque solution for trimming


  • 0
    H
        public int widthOfBinaryTree(TreeNode root) {
            if(root==null) return 0;
            Deque<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            int max = 0;
            while(!queue.isEmpty()){
                while(!queue.isEmpty() && queue.getFirst()==null){
                    queue.poll();
                }
                while(!queue.isEmpty() && queue.getLast()==null){
                    queue.pollLast();
                }
                max = Math.max(max, queue.size());
                int parentSize = queue.size();
                for(int i=0;i<parentSize;i++){
                    TreeNode parent = queue.poll();
                    if(parent!=null){
                        queue.add(parent.left);
                        queue.add(parent.right);
                    }else {
                        queue.add(null);
                        queue.add(null);
                    }
    
                }
            }
            return max;
        }
    
    

Log in to reply
 

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