Daily LeetCode – day0029 0662. Maximum Width of Binary Tree

// 0662. Maximum Width of Binary Tree
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        Queue<Pair> queue = new LinkedList<>();
        queue.offer(new Pair(root, 0L));
        long maxWidth = 1L;
        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            long left = 0L;
            long right = 0L;
            for (int i = 0; i < queueSize; ++i) {
                Pair pair = queue.poll();
                TreeNode node = pair.node;
                long index = pair.index;
                if (i == 0) left = index;
                right = index;
                if (node.left != null) {
                    queue.offer(new Pair(node.left, (index << 1) + 1));
                }
                if (node.right != null) {
                    queue.offer(new Pair(node.right, (index << 1) + 2));
                }
            }
            if (right - left + 1 > maxWidth) {
                maxWidth = right - left + 1;
            }
        }
        return (int) maxWidth;
    }
}

class Pair {
    TreeNode node;
    long index;

    public Pair(TreeNode node, Long index) {
        this.node = node;
        this.index = index;
    }
}

学习笔记：
这是一道二叉树的题目，我使用了宽度优先搜索。
一开始的写法我用了宽度优先搜索，把null的结点也都全部塞进去一起遍历了，这样做的后果就是超时了……
然后我就尝试把结点的下标也都放进去一起，这样就不需要空节点了，但是怎么捆绑呢，想到了用C++的Pair，但是java的Pair是在外置的模块里面，放进去一跑编译都通不过。
实在无奈，就手写了一个Pair类，1ms跑完，超过99.9%还是比较满意的。
这里用了一个日常小技巧，乘以2写成左移1位。