题解 | #二叉树的最大宽度#
二叉树的最大宽度
https://www.nowcoder.com/practice/0975d62a307549cea32f353f354a7377
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
if(root == null){
return 0;
}
root.val = 1;
// 对树中所有节点进行编号,左节点2n，右节点2n+1
pre(root);
// 声明一个队列存储节点
Deque<TreeNode> deque = new ArrayDeque<>();
// 声明一个map存储节点以及节点所在的层数，key：节点，value：层数
Map<TreeNode, Integer> map = new HashMap<>();
// 根节点入队，入map
deque.add(root);
map.put(root, 1);
// 初始化层数、最大宽度
int level = 1;
int maxWidth = 0;
while(!deque.isEmpty()){
// 节点出队
TreeNode curNode = deque.poll();
// 获取出队节点所在层数
Integer curLevel = map.get(curNode);
// 获取当前层数最左侧索引
int index = (int) Math.pow(2, curLevel - 1);
// 如果节点所在层与当前层数一致
if(curLevel == level){
// 计算最大宽度
maxWidth = Math.max(maxWidth, curNode.val - index + 1);
} else{
// 如果不一致，层数加一
level++;
// 重新计算最大宽度
maxWidth = Math.max(maxWidth, 1);
}
// 左节点不为空，入队列，入map
if(curNode.left != null){
deque.add(curNode.left);
map.put(curNode.left, curLevel+1);
}
// 右节点不为空，入队列，入map
if(curNode.right != null){
deque.add(curNode.right);
map.put(curNode.right, curLevel+1);
}
}
return maxWidth;
}
public void pre(TreeNode root){
if(root.left != null){
root.left.val = root.val * 2;
pre(root.left);
}
if(root.right != null){
root.right.val = root.val * 2 + 1;
pre(root.right);
}
}
}
#BFS#
vivo公司福利 700人发布
查看11道真题和解析