BFS+offsetMapping solution with comments


  • 0
    M
    public int widthOfBinaryTree(TreeNode root) {
        // BFS + offsets mapping to calculate width for the level
        
        //edge case
        if (root == null) {
            return 0;
        }
        
        // queue to store node in each level
        Queue<TreeNode> queue = new LinkedList<>();
        
        //node to offset mapping
        Map<TreeNode, Integer> map = new HashMap<>();
        
        // init root
        queue.offer(root);
        map.put(root, 0);
        
        //init global max
        int maxWidth = 1;
        
        //leave the loop when no nodes left (after processing last level)
        while (!queue.isEmpty()) {
            
            // num of nodes in current level
            int size = queue.size();
            
            //left most index
            int leftMost = 0;
            //right most index
            int rightMost = 0;
            
            //BFS rule
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                
                //set left most index
                if (i == 0) {
                    leftMost = map.get(cur);
                }
                
                //set right most index
                if (i == size - 1) {
                    rightMost = map.get(cur);
                }
                
                if (cur.left != null) {
                    queue.offer(cur.left);
                    
                    //update offsets mapping: three cases
                    if (map.get(cur) == 0) {// in root
                        map.put(cur.left, -1);
                    } else if (map.get(cur) > 0){// parent node is in right side
                        map.put(cur.left, map.get(cur) * 2 - 1);
                    } else {// parent node is in left side
                        map.put(cur.left, map.get(cur) * 2);
                    }
                    
                }
                
                if (cur.right != null) {
                    queue.offer(cur.right);
                    
                    //update offsets mapping: three cases
                    if (map.get(cur) == 0) {//root
                        map.put(cur.right, 1);
                    } else if (map.get(cur) > 0){// parent node is in right side
                        map.put(cur.right, map.get(cur) * 2);
                    } else {// parent node is in left side
                        map.put(cur.right, map.get(cur) * 2 + 1);
                    }
                }
            }
            
            //two cases, leftMost and rightMost are on side or not
            maxWidth = Math.max(maxWidth, rightMost < 0 || leftMost > 0 ? rightMost - leftMost + 1 : rightMost - leftMost);
            
        }
        
        return maxWidth;
    }

Log in to reply
 

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