662. 不懂Maximum Width of Binary T

https://leetcode-cn.com/problems/maximum-width-of-binary-tree/

（图片来源https://leetcode-cn.com/problems/maximum-width-of-binary-tree/

）

Thoughts

1. 满树中，根节点序号为idx，则左子节点为2idx，右子节点为2idx+1；
2. width = max(每一层中最右边的节点编号 - 最左边的节点编号 + 1)

非递归

public int widthOfBinaryTree(TreeNode root) {
        if(root == null) {
            return 0;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();  // 注意不要写成Queue<TreeNode>, 否则没有peekLast/peekFirst方法
        root.val = 1;
        queue.offer(root);
        int res = 0;

        while(! queue.isEmpty()) {
            res = Math.max(res, queue.peekLast().val-queue.peekFirst().val+1);
            int size = queue.size();
            for(int i=0; i<size; i++) {
                TreeNode node = queue.poll();
                if(node.left != null) {
                    node.left.val = 2 * node.val;
                    queue.offer(node.left);
                }

                if(node.right != null) {
                    node.right.val = 2 * node.val + 1;
                    queue.offer(node.right);
                }
            }
        }

        return res;
    }