给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

示例 1:

输入: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
示例 2:

输入: 

          1
         /  
        3    
       / \       
      5   3     

输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。
示例 3:

输入: 

          1
         / \
        3   2 
       /        
      5      

输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。
示例 4:

输入: 

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
输出: 8
解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。

 

 

思路：

层序的思想  每一层记录最左位置left  在同一层更新res的值  具体看代码

        public static class ReturnType {
		TreeNode node;
		int depth;
		int pos;   //深度   位置

		ReturnType(TreeNode n, int d, int p) {
			node = n;
			depth = d;
			pos = p;
		}
	}

	public int widthOfBinaryTree(TreeNode root) {
		Queue<ReturnType> queue = new LinkedList();
		//初始化  加入第0层
        queue.add(new ReturnType(root, 0, 0));
        int curDepth = 0;
        int left = 0;
        int res = 0;
        while (!queue.isEmpty()) {
            ReturnType cur = queue.poll();
            if (cur.node != null) {
            	//加入左右孩子  
                queue.add(new ReturnType(cur.node.left, cur.depth + 1, cur.pos * 2));
                queue.add(new ReturnType(cur.node.right, cur.depth + 1, cur.pos * 2 + 1));
                //来到下一层第一个的的时候进行更新
                if (curDepth != cur.depth) {
                    curDepth = cur.depth;
                    left = cur.pos;
                }
                res = Math.max(res, cur.pos - left + 1);
            }
        }
        return res;
	}