662. Maximum Width of Binary Tree

一道神奇的题，刚一看的时候感觉很简单，仔细想想发现有点意思
这个题的点在于bfs只知道自己同一层有哪些点，而不知道这些点具体的相对位置
一个特别厉害的发明是用tree在Array index里面的表示方法，若n 是当前点
2*n + 1是left child，2*n + 2是right child

这样每一层的所有index是在一定的range里面的
用dfs carry每一层的level信息和当前点的index，carry leftMost和rightMost array分别表示每一层的最左点和最右点，不断更新这两个Array和global width max = rightMost(level) - leftMost(left) + 1
最后返回max就行

63.50 %

class Solution {
    private int max;
    public int widthOfBinaryTree(TreeNode root) {
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        dfsHelper(root, 0, 0, left, right);
        return max;
    }
    //return the max level width
    private void dfsHelper(TreeNode root, int level, int idx, List<Integer> left, List<Integer> right) {
        if (root == null) return;
        if (left.size() <= level) {
            left.add(idx);
            right.add(idx);
        } else {
            right.set(level, idx);
        }
        dfsHelper(root.left, level + 1, idx * 2 + 1, left, right);
        dfsHelper(root.right, level + 1, idx * 2 + 2, left, right);
        max = Math.max(right.get(level) - left.get(level) + 1, max);
    }
 
}