Java二叉树的最大宽度详解版

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（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)。

思路：
1.使用队列Deque将树中的每一层放入队列（层序遍历）
Deque才有getLast()，getFirst()方法（后序会用到）
2.修改节点的val值为树中的序列
左孩子：双亲节点序列X2 右孩子：双亲节点序列X2+1
3.每层的宽度=队列中最后一个节点.val - 队列中第一个节点.val + 1
getLast()，getFirst()方法
4.树最大宽度为每层宽度的最大值

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        Deque queue = new LinkedList();//Deque才有getLast()，getFirst()方法
        int widthest = 0;//最大宽度
        TreeNode cur = null;
        root.val = 1;//重置root.val为root的序号
        queue.offer(root);
        //遍历每层
        while(!queue.isEmpty()){
            int width=queue.getLast().val-queue.getFirst().val+1;//每层的宽度
            widthest = (width > widthest) ? width : widthest;
            int size = queue.size();
            //一层的节点遍历
            while(size != 0){
                cur = queue.poll();
                if(cur.left != null) {
                    cur.left.val = cur.val*2;//将node的val直接变成节点在书中的序列
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    cur.right.val = cur.val*2 + 1;
                    queue.offer(cur.right);
                }
                size--;
            }
        }
        return widthest;
    }
}