二叉树的最大宽度

LeetCode 662 二叉树的最大宽度

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。
这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

import java.util.LinkedList;
import java.util.Queue;

/**
 * 执行结果：通过
 * 执行用时：1 ms, 在所有 Java 提交中击败了99.85%的用户
 * 内存消耗：40.8 MB, 在所有 Java 提交中击败了76.34%的用户
 * 通过测试用例：113 / 113
 *
 */
public class MaximumWidthOfBinaryTree {

    class InfoNode {
        public int pos;
        public TreeNode node;

        public InfoNode() {
        }

        public InfoNode(int pos) {
            this.pos = pos;
        }

        public InfoNode(int pos, TreeNode node) {
            this.pos = pos;
            this.node = node;
        }A
    }

    public int widthOfBinaryTree(TreeNode root) {
        if (null == root) {
            return 0;
        }
        Queue<InfoNode> queue = new LinkedList<InfoNode>();
        queue.add(new InfoNode(0, root));
        int max = Integer.MIN_VALUE;
        while (!queue.isEmpty()) {
            int size = queue.size();
            int left = 0;
            int right = 0;
            for (int i = 0; i < size; i++) {
                InfoNode poll = queue.poll();
                if (i == 0) {
                    left = poll.pos;
                }
                if (i == size - 1) {
                    right = poll.pos;
                }
                if (poll.node.left != null) {
                    queue.add(new InfoNode(2 * poll.pos, poll.node.left));
                }
                if (poll.node.right != null) {
                    queue.add(new InfoNode(2 * poll.pos+1, poll.node.right));
                }
            }
            max = Math.max(max,right-left+1);
        }
        return max;
    }

}