AlgoPressAppearance
0662-二叉树最大宽度
题目描述
https://leetcode.cn/problems/maximum-width-of-binary-tree
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（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)。
注意: 答案在32位有符号整数的表示范围内。
思路
使用BFS遍历，但是题目要求空节点也加入计算宽度。 所以我们还需要记录节点所在那一行的索引。
使用包装对象，将节点和 index 一起存入 queue中，在使用BFS展开。
csharp
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
class WrapNode{
public TreeNode Node;
public int Index;
public WrapNode(TreeNode node, int index){
Node = node;
Index = index;
}
}
public int WidthOfBinaryTree(TreeNode root) {
if(root == null){
return 0;
}
int len = 1;
//BFS展开
Queue<WrapNode> queue = new Queue<WrapNode>();
int level = 1;
WrapNode node = new WrapNode(root,1);
queue.Enqueue(node);
while(queue.Count > 0){
//展开
int left = 0;
int right = 0;
int count = queue.Count; //每一轮的固定数量
for(int i=0; i<count; i++){
node = queue.Dequeue();
if(i == 0){
left = node.Index;
}
if(i == count-1){
right = node.Index;
}
//入队
if(node.Node.left != null){
queue.Enqueue(new WrapNode(node.Node.left, node.Index * 2));
}
if(node.Node.right != null){
queue.Enqueue(new WrapNode(node.Node.right, node.Index * 2+1));
}
}
//Console.WriteLine("left={0},right={1}",left,right);
len = Math.Max(right - left + 1, len);
}
return len;
}
}