662. 二叉树最大宽度

参考题解
层序遍历,给节点的值编号,给每个节点一个 position 值,如果我们走向左子树,那么 position -> position * 2,如果我们走向右子树,那么 position -> positon * 2 + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null) { return 0;}
int maxWidth = 0;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
root.val = 0;
while (!queue.isEmpty()) {
int curWidth = queue.getLast().val - queue.getFirst().val + 1;
for (int i = queue.size(); i > 0 ; --i) {
TreeNode cur;
cur = queue.poll();
if (cur.left != null) {
queue.add(cur.left);
cur.left.val = cur.val*2;
}
if (cur.right != null) {
queue.add(cur.right);
cur.right.val = cur.val*2 + 1;
}
}
if (curWidth > maxWidth) {
maxWidth = curWidth;
}
}
return maxWidth;
}
}

662. 二叉树最大宽度
https://pisces34.github.io/2022/02/08/leetcode/662/
发布于
2022年2月8日
许可协议