662 Maximum Width of Binary Tree

662. Maximum Width of Binary Tree

1. Question

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where thenullnodes between the end-nodes are also counted into the length calculation.

Example 1:

Input:


           1
         /   \
        3     2
       / \     \  
      5   3     9 


Output:
 4

Explanation:
 The maximum width existing in the third level with the length 4 (5,3,null,9).

Example 2:

Input:


          1
         /  
        3    
       / \       
      5   3     


Output:
 2

Explanation:
 The maximum width existing in the third level with the length 2 (5,3).

Example 3:

Input:


          1
         / \
        3   2 
       /        
      5      


Output:
 2

Explanation:
 The maximum width existing in the second level with the length 2 (3,2).

Example 4:

Input:

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7

Output:
 8

Explanation:
The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).

Note:Answer will in the range of 32-bit signed integer.

2. Implementation

(1) BFS

class Solution {
    class NodeInfo {
        TreeNode node;
        int pos;

        public NodeInfo(TreeNode node, int pos) {
            this.node = node;
            this.pos = pos;
        }
    }
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<NodeInfo> queue = new LinkedList<>();
        queue.add(new NodeInfo(root, 1));

        int start = 0, end = 0, size = 0, maxWidth = 0;

        while (!queue.isEmpty()) {
            size = queue.size();
            start = queue.peek().pos;

            for (int i = 0; i < size; i++) {
                NodeInfo curNodeInfo = queue.remove();
                end = curNodeInfo.pos;

                if (curNodeInfo.node.left != null) {
                    queue.add(new NodeInfo(curNodeInfo.node.left, 2 * end));
                }

                if (curNodeInfo.node.right != null) {
                    queue.add(new NodeInfo(curNodeInfo.node.right, 2 * end + 1));
                }
            }
            maxWidth = Math.max(maxWidth, end - start + 1);
        }
        return maxWidth;
    }
}

3. Time & Space Complexity

BFS: 时间复杂度O(n), 空间复杂度O(w)