题目

给你一棵二叉树的根节点 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);}
}