662. 二叉树最大宽度
题目描述
输入一棵二叉树的根节点 root，用层序数组表示，null 表示空位。
把这棵树想象成按满二叉树的位置排布。对每一层，取最左边和最右边的非空节点作为两端，两端之间所有的位置（包括其中本该在满二叉树里但实际为空的位置）都计入这一层的宽度。
返回所有层中宽度的最大值。题目保证答案在 32 位有符号整数范围内。
示例 1
输入：root = [1,3,2,5,3,null,9] 输出：4
解释：第 3 层从 5 到 9 共占 4 个位置。
示例 2
输入：root = [1,3,2,5,null,null,9,6,null,7] 输出：7
解释：第 4 层两端是 6 和 7，中间有 5 个空位，宽度为 7。
示例 3
输入：root = [1,3,2,5] 输出：2
解释：第 2 层的 3 和 2 宽度为 2。
数据范围
- 节点数在
[1, 3000]范围内。 -100 <= Node.val <= 100
解题思路：广度优先搜索 + 位置编号
给节点编号：父节点编号为 p，左孩子 2p，右孩子 2p+1（和堆的数组下标一样）。按层 BFS，每层宽度 = 最右编号 - 最左编号 + 1。树很深时编号会指数增长，所以每层先把编号减去本层最左编号（归一化），再生成下一层编号，就不会溢出。
为什么正确
同一层内两个节点的编号差等于它们在满二叉树中的位置差；对整层编号同时减去一个常数不改变这个差。
复杂度分析
时间 O(n)，空间 O(n)（最宽一层的节点数）。
易错点
不能只数每层的非空节点个数，中间的空位也算宽度。另外，一条 3000 层的单链会让编号达到 2^3000，在 C++/Java/Go/JS 中必溢出，必须每层归一化。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
ans = 0
level = [(root, 0)]
while level:
first = level[0][1]
ans = max(ans, level[-1][1] - first + 1)
nxt = []
for node, pos in level:
p = pos - first
if node.left:
nxt.append((node.left, 2 * p))
if node.right:
nxt.append((node.right, 2 * p + 1))
level = nxt
return ansclass Solution {
public int widthOfBinaryTree(TreeNode root) {
long ans = 0;
List<TreeNode> nodes = new ArrayList<>();
List<Long> poss = new ArrayList<>();
nodes.add(root); poss.add(0L);
while (!nodes.isEmpty()) {
long first = poss.get(0);
ans = Math.max(ans, poss.get(poss.size() - 1) - first + 1);
List<TreeNode> nn = new ArrayList<>();
List<Long> np = new ArrayList<>();
for (int i = 0; i < nodes.size(); i++) {
TreeNode node = nodes.get(i);
long p = poss.get(i) - first;
if (node.left != null) {
nn.add(node.left); np.add(2 * p);
}
if (node.right != null) {
nn.add(node.right); np.add(2 * p + 1);
}
}
nodes = nn; poss = np;
}
return (int) ans;
}
}class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
unsigned long long ans = 0;
vector<pair<TreeNode*, unsigned long long>> level = {{root, 0}};
while (!level.empty()) {
unsigned long long first = level[0].second;
ans = max(ans, level.back().second - first + 1);
vector<pair<TreeNode*, unsigned long long>> nxt;
for (auto& [node, pos] : level) {
unsigned long long p = pos - first;
if (node->left)
nxt.push_back({node->left, 2 * p});
if (node->right)
nxt.push_back({node->right, 2 * p + 1});
}
level = nxt;
}
return (int)ans;
}
};func widthOfBinaryTree(root *TreeNode) int {
type item struct {
node *TreeNode
pos int
}
ans := 0
level := []item{{root, 0}}
for len(level) > 0 {
first := level[0].pos
ans = max(ans, level[len(level)-1].pos-first+1)
nxt := []item{}
for _, it := range level {
p := it.pos - first
if it.node.Left != nil {
nxt = append(nxt, item{it.node.Left, 2 * p})
}
if it.node.Right != nil {
nxt = append(nxt, item{it.node.Right, 2*p + 1})
}
}
level = nxt
}
return ans
}var widthOfBinaryTree = function(root) {
let ans = 0;
let level = [[root, 0]];
while (level.length) {
const first = level[0][1];
ans = Math.max(ans, level[level.length - 1][1] - first + 1);
const nxt = [];
for (const [node, pos] of level) {
const p = pos - first;
if (node.left)
nxt.push([node.left, 2 * p]);
if (node.right)
nxt.push([node.right, 2 * p + 1]);
}
level = nxt;
}
return ans;
};function widthOfBinaryTree(root: TreeNode | null): number {
let ans = 0;
let level: [TreeNode, number][] = [[root!, 0]];
while (level.length) {
const first = level[0][1];
ans = Math.max(ans, level[level.length - 1][1] - first + 1);
const nxt: [TreeNode, number][] = [];
for (const [node, pos] of level) {
const p = pos - first;
if (node.left)
nxt.push([node.left, 2 * p]);
if (node.right)
nxt.push([node.right, 2 * p + 1]);
}
level = nxt;
}
return ans;
}其他解法
两种解法的编号方式相同，只是求每层最左、最右编号的方式不同：广度优先搜索直接按层取首尾，深度优先搜索靠先左后右的顺序记下每层最左编号。
解法 2：深度优先搜索 + 位置编号 时间 O(n)，空间 O(n)
仍然按完全二叉树编号：左孩子是 2·pos，右孩子是 2·pos + 1。先左后右地深度优先搜索，每一层第一次到达的节点就是该层最左节点，用 first[depth] 记下它的编号。之后该层每个节点的宽度是 pos − first[depth] + 1，取最大值。为防编号溢出，向下传递时先减去 first[depth]，只保留相对编号。
不需要队列保存整层节点，空间取决于树高。代价是要依赖“先左后右”的遍历顺序才能得到每层最左节点，树很深时递归栈也会很深。
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
first = []
ans = 0
def dfs(node, depth, pos):
nonlocal ans
if not node:
return
if depth == len(first):
first.append(pos)
p = pos - first[depth]
ans = max(ans, p + 1)
dfs(node.left, depth + 1, 2 * p)
dfs(node.right, depth + 1, 2 * p + 1)
dfs(root, 0, 0)
return ansclass Solution {
List<Long> first = new ArrayList<>();
long ans = 0;
void dfs(TreeNode node, int depth, long pos) {
if (node == null) return;
if (depth == first.size()) first.add(pos);
long p = pos - first.get(depth);
ans = Math.max(ans, p + 1);
dfs(node.left, depth + 1, 2 * p);
dfs(node.right, depth + 1, 2 * p + 1);
}
public int widthOfBinaryTree(TreeNode root) {
dfs(root, 0, 0);
return (int) ans;
}
}class Solution {
vector<long long> first;
long long ans = 0;
void dfs(TreeNode* node, int depth, long long pos) {
if (!node) return;
if (depth == (int)first.size()) first.push_back(pos);
long long p = pos - first[depth];
ans = max(ans, p + 1);
dfs(node->left, depth + 1, 2 * p);
dfs(node->right, depth + 1, 2 * p + 1);
}
public:
int widthOfBinaryTree(TreeNode* root) {
dfs(root, 0, 0);
return (int)ans;
}
};func widthOfBinaryTree(root *TreeNode) int {
first := []int{}
ans := 0
var dfs func(node *TreeNode, depth, pos int)
dfs = func(node *TreeNode, depth, pos int) {
if node == nil {
return
}
if depth == len(first) {
first = append(first, pos)
}
p := pos - first[depth]
ans = max(ans, p+1)
dfs(node.Left, depth+1, 2*p)
dfs(node.Right, depth+1, 2*p+1)
}
dfs(root, 0, 0)
return ans
}var widthOfBinaryTree = function(root) {
const first = [];
let ans = 0;
const dfs = (node, depth, pos) => {
if (!node) return;
if (depth === first.length) first.push(pos);
const p = pos - first[depth];
ans = Math.max(ans, p + 1);
dfs(node.left, depth + 1, 2 * p);
dfs(node.right, depth + 1, 2 * p + 1);
};
dfs(root, 0, 0);
return ans;
};function widthOfBinaryTree(root: TreeNode | null): number {
const first: number[] = [];
let ans = 0;
const dfs = (node: TreeNode | null, depth: number, pos: number): void => {
if (!node) return;
if (depth === first.length) first.push(pos);
const p = pos - first[depth];
ans = Math.max(ans, p + 1);
dfs(node.left, depth + 1, 2 * p);
dfs(node.right, depth + 1, 2 * p + 1);
};
dfs(root, 0, 0);
return ans;
}