Java BFS solution using dummy nodes


  • 0
    A

    The basic idea is the following:

    1. When we remove a node from the queue, we simply go ahead and add both of its children to the queue, even if they are null. If we subsequently remove a null value from the queue, then we add two nulls to the queue.
    2. After adding all nodes for a particular level, trim the ends of the queue and remove any nulls. Then we will have a queue that is bounded by two actual nodes and will represent the width for that level.
    3. Return the level with the max width.

    I represent the queue using a LinkedList since it allows null inserts.

    class Solution {
        public int widthOfBinaryTree(TreeNode root)
        {
            if(root == null)
            {
                return 0;
            }
            LinkedList<TreeNode> q = new LinkedList<TreeNode>();
            q.add(root);
            int width = 1;
            while(!q.isEmpty())
            {
                int size = q.size();
                for(int i = 0; i < size; i++)
                {
                    TreeNode n = q.remove();
                    TreeNode left = (n == null) ? null : n.left;
                    TreeNode right = (n == null) ? null : n.right;
                    q.add(left);
                    q.add(right);
                }
                trim(q);
                width = Math.max(width, q.size());
            }
            return width;
        }
        
        public void trim(LinkedList<TreeNode> q)
        {
            while(q.size() > 0 && q.getFirst() == null)
            {
                q.removeFirst();
            }
            while(q.size() > 0 && q.getLast() == null)
            {
                q.removeLast();
            }
            
        }
    }
    

  • 0
    This post is deleted!

Log in to reply
 

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