共计 2113 个字符，预计需要花费 6 分钟才能阅读完成。
题目地址：https://leetcode-cn.com/probl… 题目描述：给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的 null 节点也计入长度）之间的长度。
示例 1:
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: 4 解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。示例 2:
输入:
1
/
3
/ \
5 3
输出: 2 解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。示例 3:
输入:
1
/ \
3 2
/
5
输出: 2 解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。示例 4:
输入:
1
/ \
3 2
/ \
5 9
/ \
6 7
输出: 8 解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。
解答：这一题就是求每一层，最左边不为空的节点到最右边不为空的节点的距离。因此我们可以在层序遍历的时候把空节点 (这里的空节点指的是指的的一个特殊节点) 也加入进去，这样对于每一层不空的节点，记录下标，然后找出最大最小值，就找到每一层的最大宽度。这样虽然思路没有问题，但是对于深度很深的树会超时。。。因为，这样做的话时间复杂度是指数级别(与树的深度成指数关系)。java 超时代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) {val = x;}
* }
*/
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if(root == null)return 0;
int ans = 0;
ArrayDeque<TreeNode> deque = new ArrayDeque(500);
deque.offer(root);
while(!deque.isEmpty())
{
int n = deque.size();
int left = n,right = 0;
for(int i = 0;i < n;i++)
{
TreeNode temp = deque.poll();
if(temp.val != -9999)
{
left = Math.min(left,i);
right = i;
}
if(temp.left != null)
deque.offer(temp.left);
else deque.offer(new TreeNode(-9999));
if(temp.right != null)
deque.offer(temp.right);
else deque.offer(new TreeNode(-9999));
}
if(left == n&&right == 0)break;
ans = Math.max(ans,right-left+1);
}
return ans;
}
}
换一种思路，我们现在对这棵树进行深度优先遍历，但是遍历的时候记录下它是树的第几个节点, 并且记录下它属于第几层，然后保存在 hashmap 中，map 的键：层号，值：节点下标组成的列表，最后在访问 hashmap 找到每一层最大最小下标即找出答案。需要注意的是树的节点这样编号(如果 root 编号为 1，那么它的左子树编号为 2i, 右子树编号为 2i+1)。java ac 代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) {val = x;}
* }
*/
class Solution {
HashMap<Integer,List<Integer>> map = new HashMap(5000);
public int widthOfBinaryTree(TreeNode root) {
if(root == null)return 0;
int ans = 0;
dfs(root,1,1);
for(Map.Entry<Integer,List<Integer>> entry:map.entrySet() )
{
List<Integer> list= entry.getValue();
int min = Integer.MAX_VALUE,max = Integer.MIN_VALUE;
for(Integer i:list)
{
min = Math.min(min,i);
max = Math.max(max,i);
}
ans = Math.max(ans,max-min+1);
}
return ans;
}
void dfs(TreeNode root,int i,int level)
{
if(root == null)return;
if(map.get(level)==null)
map.put(level,new ArrayList());
map.get(level).add(i);
dfs(root.left,2*i,level+1);
dfs(root.right,2*i+1,level+1);
}
}
