二叉树的最大宽度
# 📃 题目描述
题目链接:662. 二叉树最大宽度 (opens new window)
# 🔔 解题思路
为了求宽度,不妨给二叉树编号(我这里是从 1 开始编号,从0开始也是一样的):
按层遍历,不过就是最后个节点的编号减去第一个节点的编号加 1即可。
假设当前节点编号为 root.val,那么:
- 左子节点编号: root.val * 2
- 右子节点编号: root.val * 2 + 1
比如
2
3 9
7 2 null 4
编号后为
1
2 3
4 5 null 7
最大宽度为 7 - 4 + 1 = 4
具体代码如下:
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
Queue<TreeNode> queue = new LinkedList<>();
root.val = 1;
queue.offer(root);
// 记录最大宽度
int res = Integer.MIN_VALUE;
while (!queue.isEmpty()) {
int size = queue.size();
// 当前层的最小序号、最大序号
int l = 0, r = 0;
for (int i = 0; i < size; i ++) {
TreeNode cur = queue.poll();
if (i == 0) {
l = cur.val;
}
if (i == size - 1) {
r = cur.val;
res = Math.max(res, r - l + 1);
}
if (cur.left != null) {
cur.left.val = cur.val * 2;
queue.offer(cur.left);
}
if (cur.right != null) {
cur.right.val = cur.val * 2 + 1;
queue.offer(cur.right);
}
}
}
return res;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10