662. 二叉树最大宽度

题目

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

题目数据保证答案将会在 32 位 带符号整数范围内。

示例 1：

输入： root = [1,3,2,5,3,null,9]
输出： 4
解释： 最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。

代码与解析

不得不说三叶姐姐真牛掰，我有想过用高度和编号，但就卡在了编号怎么弄。三叶姐姐解答： 左侧编号是u << 1, 右侧编号是 u<<1 | 1，就是扩大2倍，|1是将最高位置为1，例如第二层，左边就是01，右边就是11这样子

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    int ans = 0;
    public int widthOfBinaryTree(TreeNode root) {
        dfs(root, 1, 0);
        return ans;
    }
    public void dfs(TreeNode node, int u, int height) {
        if(node == null)    return;
        if(!map.containsKey(height)) map.put(height, u);
        u = u - map.get(height) + 1; //防止编号溢出
        ans = Math.max(ans, u);
        dfs(node.left, u << 1, height + 1);
        dfs(node.right, u << 1 | 1, height + 1);
    }
}