友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
662. 二叉树最大宽度
给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
示例 1：
输入：root = [1,3,2,5,3,null,9] 输出：4 解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。
示例 2：
输入：root = [1,3,2,5,null,null,9,6,null,7] 输出：7 解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。
示例 3：
输入：root = [1,3,2,5] 输出：2 解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。
提示：
-
树中节点的数目范围是
[1, 3000] -
-100 <= Node.val <= 100
思路分析
使用伪节点进行广度优先遍历超时！
从上到下，每个节点都有一个编号，如果父节点是 x，则左节点是 2x，而右节点是 2x+1，因为父节点可以这个节点编号传递下去，这样不需要关注空节点。把每一层节点放入到一个队列中，尾部节点的编号减去头部节点编号再加 1 就是每层的宽度。
还有一个深度优先遍历的解法：
-
一刷（超时）
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* 通过 94 / 116 个测试用例，但超时了。
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-20 21:13:45
*/
public int widthOfBinaryTree(TreeNode root) {
final TreeNode DUMMY = new TreeNode(Integer.MAX_VALUE);
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int result = 0;
while (!queue.isEmpty()) {
int size = queue.size();
result = Math.max(result, size);
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
} else {
queue.offer(DUMMY);
}
if (node.right != null) {
queue.offer(node.right);
} else {
queue.offer(DUMMY);
}
}
while (!queue.isEmpty() && queue.peek() == DUMMY) {
queue.poll();
}
while (!queue.isEmpty() && queue.peekLast() == DUMMY) {
queue.pollLast();
}
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-20 21:37:22
*/
public int widthOfBinaryTree(TreeNode root) {
Deque<Pair<TreeNode, Integer>> nodes = new LinkedList<>();
int result = 0;
nodes.add(new Pair<>(root, 1));
while (!nodes.isEmpty()) {
result = Math.max(result,
nodes.getLast().value - nodes.getFirst().value + 1);
int size = nodes.size();
for (int i = 0; i < size; i++) {
Pair<TreeNode, Integer> pair = nodes.poll();
if (pair.key.left != null) {
nodes.offer(new Pair<>(pair.key.left, pair.value * 2));
}
if (pair.key.right != null) {
nodes.offer(new Pair<>(pair.key.right, pair.value * 2 + 1));
}
}
}
return result;
}
private static class Pair<K, V> {
K key;
V value;
public Pair(K key, V value) {
this.key = key;
this.value = value;
}
}