Maximum Width of Binary Tree

题目

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.

思路分析

这道题的第一印象应该使用BFS来做，因为题目中说width指的是每一行的length。这道题的难点在于进行BFS进行level order traverse的时候要记住每一个节点在这一行的position，记住了每个节点的position，那么我们就可以通过计算最左边的节点与最右边的节点位置差来得到这一行的length。所以这道题的实现要注意以下两点：

• 一般的BFS是用一个queue来记录节点，这道题还要再用一个queue来记录节点所处的行的位置
• 如何找到最左边节点与最右边节点的位置，通过index来找到

//Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> nodeQueue = new LinkedList<>();      <<<<<One queue to record tree nodes
        Queue<Integer> positionQueue = new LinkedList<>();   <<<<<One queue to record the node position
        nodeQueue.offer(root);
        positionQueue.offer(0);
        int maxWidth = 1;
        int leftPosition = 0;
        int rightPosition = 0;
        while(!nodeQueue.isEmpty()) {
            int size = nodeQueue.size();
            for (int index=0; index<size; index++){
                TreeNode curNode = nodeQueue.poll();
                int position = positionQueue.poll();
                if(index == 0) leftPosition = position;       <<<<<Obtain the left most position
                if(index == size-1) rightPosition = position; <<<<<Obtain the right most position
                if(curNode.left != null){
                    nodeQueue.offer(curNode.left);
                    positionQueue.offer(position*2);
                }
                if(curNode.right != null) {
                    nodeQueue.offer(curNode.right);
                    positionQueue.offer(position*2 + 1);
                }
            }
            maxWidth = maxWidth > (rightPosition-leftPosition+1) ? maxWidth: (rightPosition-leftPosition+1);
        }
        return maxWidth;
    }
}