给定一个二叉树，请你求出此二叉树的最大宽度。
本题中树第 i 层的宽度定义为：第 i 层最左边的节点到最右边之间的距离，中间空节点也计入距离。
例如：
本树中第 1 层只有一个节点，故第 1 层宽度是 1 ，第二层最左侧到最右侧的距离是 2 ，所以宽度是 2 ， 第三层最左侧 4 到最右侧 5 距离是 4 ，故宽度是 4，此树最大宽度是 4。
[编程题]二叉树的最大宽度
import java.util.*;
public class Solution {
public int widthOfBinaryTree (TreeNode root) {
// BFS
if (root == null) return 0;
int width = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size(), left = -1, right = -1; // left、right该层最左、右节点下标
for (int i = 0; i < size; i++) {
TreeNode t = queue.poll();
if (t.val == -1) { // -1节点顶替空节点
queue.offer(new TreeNode(-1));
queue.offer(new TreeNode(-1));
} else {
if (left == -1) left = i;
else right = i;
if (t.left == null) queue.offer(new TreeNode(-1));
else queue.offer(t.left);
if (t.right == null) queue.offer(new TreeNode(-1));
else queue.offer(t.right);
}
}
if (left == -1 && right == -1) break;
width = Math.max(width, right == -1 ? 1 : right - left + 1);
}
return width;
}
}
发表于 2025-04-03 08:31:44
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
/**
* NC204 二叉树的最大宽度
* @author d3y1
*/
public class Solution {
private int result = 0;
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
public int widthOfBinaryTree (TreeNode root) {
return solution1(root);
// return solution2(root);
}
/**
* 迭代: 层序遍历
* @param root
* @return
*/
private int solution1(TreeNode root){
levelOrder(root);
return result;
}
/**
* 层序遍历
* @param root
*/
private void levelOrder(TreeNode root){
if(root == null){
return;
}
// 双端队列
// deque.offer(tNode) -> tNode 不能为 null
// Deque<TreeNode> deque = new ArrayDeque<>();
// deque.offer(tNode) -> tNode 可以为 null
Deque<TreeNode> deque = new LinkedList<>();
deque.offerLast(root);
int size;
TreeNode tNode;
while(!deque.isEmpty()){
// 去掉该层左边空节点(first端)
while(!deque.isEmpty() && deque.peekFirst()==null){
deque.pollFirst();
}
// 去掉该层右边空节点(last端)
while(!deque.isEmpty() && deque.peekLast()==null){
deque.pollLast();
}
// 节点个数即为宽度
size = deque.size();
result = Math.max(result, size);
// 生成下一层
while(size-- > 0){
tNode = deque.pollFirst();
if(tNode != null){
deque.offerLast(tNode.left);
deque.offerLast(tNode.right);
}else{
deque.offerLast(null);
deque.offerLast(null);
}
}
}
}
private HashMap<Integer,Integer> leftIdxMap = new HashMap<>();
/**
* 递归: 前序遍历
* @param root
* @return
*/
private int solution2(TreeNode root){
preOrder(root, 1, 1);
return result;
}
/**
* 前序遍历
* @param root
* @param level
* @param currIdx
*/
private void preOrder(TreeNode root, int level, int currIdx){
if(root == null){
return;
}
// key(level)存在-直接取值 key(level)不存在-先put,再取值
int leftIdx = leftIdxMap.computeIfAbsent(level, value->currIdx);
result = Math.max(result, currIdx-leftIdx+1);
preOrder(root.left, level+1, 2*currIdx);
preOrder(root.right, level+1, 2*currIdx+1);
}
}
发表于 2025-01-15 13:22:22
回复(0)
java 层序遍历，加上一个队列记录非空节点的索引即可
public int widthOfBinaryTree (TreeNode root) {
// write code here
if(root == null)
return 0;
// 记录非空节点
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
// 记录非空节点对应的索引
Deque<Integer> indexQ = new ArrayDeque<>();
indexQ.offer(1);
int ans = 0;
while(!queue.isEmpty()){
int size = queue.size();
int leftIdx = -1;
for(int i=0;i<size;i++){
TreeNode cur = queue.poll();
int pos = indexQ.poll();
// 记录最左边的非空节点
if(leftIdx == -1){
leftIdx = pos;
}
// 实时更新该层的最大宽度
ans = Math.max(ans, pos-leftIdx+1);
// 补充下一层的节点入队,空节点也需要入队
if(cur.left != null){
queue.offer(cur.left);
indexQ.offer(pos*2);
}
if(cur.right != null){
queue.offer(cur.right);
indexQ.offer(pos*2+1);
}
}
}
return ans;
}
发表于 2022-07-28 11:53:55
回复(0)
一个比较好想的方法：利用完全二叉树的性质进行求解
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
public int widthOfBinaryTree (TreeNode root) {
if (root == null) return 0;
root.val = 0;
// 对二叉树节点按照完全二叉树重新赋值
preTravel(root);
Deque<TreeNode> deque = new ArrayDeque<>();
deque.add(root);
int res = 1; // 最大宽度
// 广度优先遍历，计算每一层最后一个非空节点与第一个非空节点的差值，并更新最大宽度
while (!deque.isEmpty()) {
int n = deque.size();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
TreeNode node = deque.pop();
list.add(node.val);
if (node.left != null) deque.add(node.left);
if (node.right != null) deque.add(node.right);
}
res = Math.max(res, list.get(list.size() - 1) - list.get(0) + 1);
}
return res;
}
/**
* 按照完全二叉树给节点赋值，即根节点 = 0；左子节点 = 父节点 * 2 + 1；右子节点 = 父节点 * 2 + 2
*/
public void preTravel(TreeNode root) {
if (root.left != null) {
root.left.val = 2 * root.val + 1;
preTravel(root.left);
}
if (root.right != null) {
root.right.val = 2 * root.val + 2;
preTravel(root.right);
}
}
}
发表于 2022-07-09 20:28:47
回复(0)
import java.util.*;
public class Solution {
class IndexTreeNode {
public Integer val;
public Integer index;
public IndexTreeNode left;
public IndexTreeNode right;
public IndexTreeNode (TreeNode node, Integer index) {
this.val = node.val;
this.index = index;
this.left = node.left == null ? null : new IndexTreeNode(node.left, 2 * index + 1);
this.right = node.right == null ? null : new IndexTreeNode(node.right, 2 * index + 2);
}
}
public int widthOfBinaryTree (TreeNode root) {
if (root == null) {
return 0;
}
int ans = 1;
Queue<IndexTreeNode> queue = new LinkedList<>();
queue.offer(new IndexTreeNode(root, 0));
while (!queue.isEmpty()) {
IndexTreeNode head = null;
IndexTreeNode tail = null;
for (int s = queue.size(); s > 0; --s) {
IndexTreeNode n = queue.poll();
IndexTreeNode[] children = new IndexTreeNode[]{ n.left, n.right };
for (IndexTreeNode child : children) {
if (child != null) {
queue.offer(child);
if (head == null) {
head = child;
}
tail = child;
}
}
}
if (head != null && tail != null) {
ans = tail.index - head.index + 1;
}
}
return ans;
}
发表于 2022-05-16 12:11:12
回复(0)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
public int widthOfBinaryTree (TreeNode root) {
// write code here
if(root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int maxWidth = 0;
while(!queue.isEmpty()){
TreeNode cur = null;
int size = queue.size();
ArrayList<TreeNode> array = new ArrayList<>();
for(int i = 0; i < size; i++){
cur = queue.poll();
array.add(cur);//将每一层的所有节点收集，包括空
if(cur != null){
queue.offer(cur.left);
queue.offer(cur.right);
}
}
int start = 0, end = 0, width = 0;
//找第一个不为空的
for(int i = 0; i < array.size(); i++){
if(array.get(i) != null) {
start = i;
break;
}
}
//找最后一个不为空的
for(int i = array.size()-1; i >= 0; i--){
if(array.get(i) != null) {
end = i;
break;
}
}
//计算宽度
//如果某一层全空，也会计算宽度为1，但不影响最终结果正确
width = end - start + 1;
//更新宽度
if(width > maxWidth)
maxWidth = width;
}
return maxWidth;
}
}最后一个样例过不了，但是我怎么觉得答案有点问题。。。
发表于 2022-01-21 11:13:44
回复(0)
一个比较好想的思路是：用队列进行BFS。考虑到每次进入while循环时，队列中都包含一层的所有节点，所以我们要把空节点的占位考虑进去的话，就可以构建一个索引队列，同步进行BFS。当往节点队列中加入左右孩子节点时，索引队列同步加入左右孩子节点的索引（通过堆中父节点与左右孩子节点的索引换算关系计算得到）。于是我们可以在每次进入while循环时就取出索引队列的尾节点索引和头节点索引（要既能取出头节点，又要能取出尾节点，就需要使用双端队列，直接用双端链表就行），计算当前层的宽度：宽度=尾节点索引-头结点索引+1，每次计算出一层的宽度就更新一遍树的最大宽度。
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
public int widthOfBinaryTree (TreeNode root) {
// write code here
LinkedList<TreeNode> queue = new LinkedList<>();
LinkedList<Integer> indexQueue = new LinkedList<>();
queue.add(root);
indexQueue.add(0);
int maxWidth = 0;
while(!queue.isEmpty()){
maxWidth = Math.max(maxWidth, indexQueue.getLast() - indexQueue.getFirst() + 1);
TreeNode node = queue.removeFirst();
int index = indexQueue.removeFirst();
if(node.left != null){
queue.add(node.left);
indexQueue.add(index << 1);
}
if(node.right != null){
queue.add(node.right);
indexQueue.add((index << 1)|1);
}
}
return maxWidth;
}
}
发表于 2021-12-16 11:03:44
回复(0)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
public int widthOfBinaryTree (TreeNode node) {
if (node == null) {
return 0;
}
// 遍历的当前节点
TreeNode currentNode = node;
// 下一层开始节点
TreeNode nextStart = null;
// 下一层结束节点
TreeNode nextEnd = node;
// 当前层结束节点
TreeNode currentEnd = node;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(node);
int count = 0;
int maxCount = 0;
while (!queue.isEmpty()) {
currentNode = queue.poll();
if (currentNode == null) {
count++;
continue;
}
if (currentNode.left != null) {
nextEnd = currentNode.left;
nextStart = nextStart != null ? nextStart : currentNode.left;
queue.add(currentNode.left);
} else {
if (currentNode.left == null && nextStart != null) {
queue.add(currentNode.left);
}
}
if (currentNode.right != null) {
nextEnd = currentNode.right;
nextStart = nextStart != null ? nextStart : currentNode.right;
queue.add(currentNode.right);
} else {
if (currentNode.right == null && nextStart != null) {
queue.add(currentNode.left);
}
}
count++;
if (currentEnd == currentNode) {
nextStart = null;
currentEnd = nextEnd;
maxCount = Math.max(count, maxCount);
count = 0;
}
}
return maxCount;
}
}
发表于 2021-12-13 01:08:44
回复(0)
问题信息
难度：
15条回答
66收藏
5185浏览
通过挑战的用户
查看代码-
2022-09-16 05:12:00
-
2022-09-15 15:46:07 -
2022-09-14 02:00:07 -
2022-09-13 12:43:19
-
2022-09-12 15:51:48
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
