给定一个二叉树，请你求出此二叉树的最大宽度。
本题中树第 i 层的宽度定义为：第 i 层最左边的节点到最右边之间的距离，中间空节点也计入距离。
例如：
本树中第 1 层只有一个节点，故第 1 层宽度是 1 ，第二层最左侧到最右侧的距离是 2 ，所以宽度是 2 ， 第三层最左侧 4 到最右侧 5 距离是 4 ，故宽度是 4，此树最大宽度是 4。
[编程题]二叉树的最大宽度
一个比较好想的思路是：用队列进行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)
用C写到了排行第五的代码
层次遍历就行了，将节点val值改为他在完全二叉树中第几的位置，用两个指针pre和front记录最左边和最右边，然后每到新的一层两数相减即可，值得注意的是，最后一层要特殊处理一下
#include <stdio.h>
int max(int a,int b)
{
if(a>b)return a;
else return b;
}
int widthOfBinaryTree(struct TreeNode* root ) {
if(root==NULL)return 0;
struct TreeNode** que=(struct TreeNode**)malloc(sizeof(struct TreeNode*)*100);
int l=-1,r=-1;
int ans=1;
que[++r]=root;
root->val=1;
struct TreeNode* front=root;
struct TreeNode* pre=root;
struct TreeNode* lateleft=NULL;
while(l<r)
{
root=que[++l];
if(root==front)
{
if(l!=0)pre=que[l-1];
ans=max(ans,pre->val-front->val+1);
front=NULL;
lateleft=root;
}
if(root->left)
{
root->left->val=root->val*2;
if(front==NULL)front=root->left;
que[++r]=root->left;
}
if(root->right)
{
root->right->val=root->val*2+1;
if(front==NULL)front=root->right;
que[++r]=root->right;
}
}
pre=que[r];
ans=max(ans,pre->val-lateleft->val+1);
return ans;
}
发表于 2023-10-14 16:21:33
回复(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)
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param root TreeNode类 # @return int整型 # class Solution: def widthOfBinaryTree(self , root: TreeNode) -> int: # write code here if not root: return False q = [] q.append(root) res = 0 while len(q) != 0: left = 0 right = len(q) while q[left] is None: left += 1 while q[right - 1] is None: right -= 1 res = max(res, right - left) next_q = [] have_next = False for index in range(len(q)): node = q[index] if node is None: next_q.append(None) next_q.append(None) continue if node.left: have_next = True next_q.append(node.left) else: next_q.append(None) if node.right: have_next = True next_q.append(node.right) else: next_q.append(None) if have_next: q = next_q else: q = [] return res
发表于 2024-04-27 23:16:50
回复(0)
package main
import _"fmt"
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
func widthOfBinaryTree( root *TreeNode ) int {
if root==nil{
return 0
}
root=label(root,1)
max:=1
q:=[]*TreeNode{root}
for len(q)>0{
new_q:=[]*TreeNode{}
for _,qi:=range q{
if qi.Left!=nil{
new_q=append(new_q,qi.Left)
}
if qi.Right!=nil{
new_q=append(new_q,qi.Right)
}
}
x:=1
if len(new_q)>1{
x=new_q[len(new_q)-1].Val-new_q[0].Val+1
}
if x>max{
max=x
}
q=new_q
}
return max
}
func label(root *TreeNode,x int)*TreeNode{
if root==nil{
return nil
}
root.Val=x
root.Left=label(root.Left,x*2)
root.Right=label(root.Right,x*2+1)
return root
}
发表于 2023-03-09 21:14:20
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int widthOfBinaryTree(TreeNode* root) {
// write code here
queue<TreeNode*> que;
que.push(root);
vector<int> nums;
nums.push_back(1);
while(que.empty()==false)
{
int size=que.size();
int count=0;
for(int i=0;i<size;i++)
{
TreeNode* node=que.front();
que.pop();
if(node->left!=nullptr)
{
que.push(node->left);
count++;}
if(node->right!=nullptr)
{
que.push(node->right);
count++;
}
}
nums.push_back(count);
}
int max=nums[0];
for(int i=0;i<nums.size();i++)
{
if(nums[i]>max)
max=nums[i];
}
return max;
}
};
做了半天只把每层非空节点的个数计算出来了，用层序遍历的方法，计算每层的个数放入到一个数组中，在数组中找出最大的数即可。
发表于 2022-12-06 20:30:14
回复(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)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int widthOfBinaryTree(TreeNode* root) {
// write code here
if(!root) return 0;
queue<pair<TreeNode*,int>> q;
q.push(make_pair(root, 0));
int res=0;
while(!q.empty()){
int size=q.size();
int l,r;
bool flag=true;
for(int i=0;i<size;++i){
int index=q.front().second;
auto p=q.front().first;
q.pop();
if(flag){
flag=false;
l=index;
r=index;
}
r=index;
if(p->left) q.push(make_pair(p->left, 2*index+1));
if(p->right) q.push(make_pair(p->right,2*index+2));
}
res=max(res,r-l+1);
}
return res;
}
};
发表于 2022-04-10 17:04:56
回复(0)
function widthOfBinaryTree( root ) {
// write code here
const queue = [[root, 0]];
let res = 0; // 全局维护最大值
let left = 0; // 记录当前层最左边节点的计数值
let right = 0; // 记录当前层最右边节点的计数值
while (queue.length) {
left = queue[0][1];
const len = queue.length;
for (let i = 0; i < len; i++) {
let [h, pos] = queue.shift();
right = pos;
if (h.left) queue.push([h.left, 2 * (pos - left)]); // 重点，优化掉左边不需要计数的部分
if (h.right) queue.push([h.right, 2 * (pos - left) + 1]);
}
res = Math.max(res, right - left + 1);
}
return res;
}
发表于 2022-03-25 15:42:41
回复(0)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int widthOfBinaryTree(TreeNode* root) {
// write code here
int res = 0;
queue<pair<TreeNode*,int>> q;
q.push(make_pair(root,0));
while(!q.empty()){
int sz = q.size();
int l = INT_MAX, r = INT_MIN;
while(sz--){
auto t = q.front();
q.pop();
TreeNode* temp = t.first;
int index = t.second;
l = min(l,index);
r = max(r,index);
if(temp->left){
q.push(make_pair(temp->left,2 * index + 1));
}
if(temp->right){
q.push(make_pair(temp->right,2 * index + 2));
}
}
res = max(res, r- l + 1);
}
return res;
}
};
层序遍历的时候记录id索引即可
发表于 2022-03-01 20:29:34
回复(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)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
void dfs(TreeNode* root,int level,vector<vector<int>>& tmp)
{
if (level > tmp.size()) tmp.push_back({});
if (!root)
{
tmp[level-1].push_back(0);
return;
}
else tmp[level-1].push_back(1);
dfs(root->left,level+1,tmp);
dfs(root->right,level+1,tmp);
}
int func(vector<int>& tmp)
{
int left = 0;
int right = tmp.size()-1;
while (left < tmp.size() && tmp[left] != 1) left++;
while (right >=0 && tmp[right] != 1) right--;
return right - left + 1;
}
int widthOfBinaryTree(TreeNode* root) {
// write code here
vector<vector<int>> tmp;
dfs(root,1,tmp);
int res = 0;
for (auto &c : tmp)
{
int len = func(c);
res = max(res,len);
}
return res;
}
}; {1,2,3,4,#,4,5,6,#,1}
这颗树画出来的最大宽度也是4，我的代码跑的也是4
为什么答案是5？
发表于 2022-01-04 11:12:04
回复(4)
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条回答
54收藏
2547浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
