# 0662. Maximum Width of Binary Tree
###### tags: `Leetcode` `Medium` `DFS` `BFS`
Link: https://leetcode.com/problems/maximum-width-of-binary-tree/
## 思路 $O(N)$ $O(N)$
一开始的想法是用层序遍历，但是这样会TLE，因为每一层末尾有没有非空的node需要一直遍历到末尾才能知道，因此会浪费很多时间

参考官方解答
在解法中，应该尽量只遍历非空的node，用dfs或者bfs都可以，给每个node一个序号，编号方式为如果一个node编号为$a$，那么它的两个child就是$2a$和$2a+1$
在dfs解法当中，用一个map存每个row的第一个非空node的编号，因为是dfs所以第一次遍历到某个row的node对应的编号就是这个row的第一个非空node的编号。在dfs的过程中，找出maxWidth
## Code

class Solution {
    Map<Long, Long> firstIdxTable;
    long maxWidth = 0;
    public int widthOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        firstIdxTable = new HashMap<>();
        dfs(root, 0, 0);
        return (int)maxWidth;
    }
    private void dfs(TreeNode root, long row, long col){
        if(root == null) return;
        if(!firstIdxTable.containsKey(row)){
            firstIdxTable.put(row, col);
        }
        maxWidth = Math.max(maxWidth, col-firstIdxTable.get(row)+1);
        dfs(root.left, row+1, 2*col);
        dfs(root.right, row+1, 2*col+1);
    }
}