题解 | #二叉树的最大宽度#

思路：本题乍一看可以用层序遍历？但是涉及到空节点的问题，层序遍历存在诸多麻烦，因此可以利用二叉树的特性：左叶子节点的序号为根节点的两倍，右叶子节点的序号为根节点的2倍加1.利用这个性质，我们把每一层的最左节点的序号加入一个map中（这个动作只进行一次即可），以后每次遍历到该层的时候，刷新该层的最大节点数即可。

public class Solution {
    int res = 0;
    Map<Integer, Integer> levelRecord = new HashMap<>();
    public int widthOfBinaryTree (TreeNode root) {
        if(root==null)return 0;
        dfs(root,0,0);
        return res;
    }
    public void dfs(TreeNode root,int depth,int index){
        if(root==null)return;
        if(levelRecord.get(depth)==null)levelRecord.put(depth,index);
        res = Math.max(res,index - levelRecord.get(depth)+1);
        dfs(root.left,depth+1,index*2);
        dfs(root.right,depth+1,index*2+1);
    }
}