662. 二叉树最大宽度

🟠   🔖  树 深度优先搜索 广度优先搜索 二叉树  🔗 力扣 LeetCode

题目

Given the root of a binary tree, return themaximum width of the given tree.

The maximum width of a tree is the maximum width among all levels.

The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end- nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

It is guaranteed that the answer will in the range of a 32-bit signed integer.

Example 1:

Input: root = [1,3,2,5,3,null,9]

Output: 4

Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

Example 2:


Input: root = [1,3,2,5,null,null,9,6,null,7]

Output: 7

Explanation: The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).

Example 3:

Input: root = [1,3,2,5]

Output: 2

Explanation: The maximum width exists in the second level with length 2 (3,2).

Constraints:

• The number of nodes in the tree is in the range [1, 3000].
• -100 <= Node.val <= 100

题目大意

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

题目数据保证答案将会在 32 位 带符号整数范围内。

示例 1：

输入： root = [1,3,2,5,3,null,9]

输出： 4

解释： 最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。

示例 2：


输入： root = [1,3,2,5,null,null,9,6,null,7]

输出： 7

解释： 最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。

示例 3：

输入： root = [1,3,2,5]

输出： 2

解释： 最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。

提示：

• 树中节点的数目范围是 [1, 3000]
• -100 <= Node.val <= 100

解题思路

这道题可以通过宽度优先搜索（BFS）来解决，借助队列，可以在遍历过程中记录每个节点的位置索引，并通过计算该层最左和最右节点的索引差异来确定最大宽度。

为了方便计算节点之间的距离，给每个节点分配一个虚拟索引。假设根节点的索引为 0，对于某个节点i，其左孩子的索引为2*i + 1，右孩子的索引为2*i + 2。这样就可以在遍历的过程中记录每一层的最左和最右索引，来计算该层的宽度：宽度 = 最右索引 - 最左索引 + 1。

1. 初始化：使用队列来进行层序遍历，队列中的每个元素是一个二元组，包含节点和节点对应的索引位置。
2. 遍历树的每一层：对于每一层，记录这一层的最左和最右节点的索引。
3. 更新最大宽度：通过计算每层的宽度来更新最大宽度。
4. 返回最大宽度：遍历完成后，返回记录的最大宽度。

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树中的节点数量。我们需要遍历每一个节点一次。
• 空间复杂度：O(n)，在最坏情况下，队列中会包含最多一整层的节点数量。

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var widthOfBinaryTree = function (root) {
	if (!root) return 0;
	let queue = [[root, 0]],
		res = 0,
		first,
		last;
	// BFS
	while (queue.length) {
		const len = queue.length;
		// 这一层的最左节点的索引
		const startIndex = queue[0][1];
		for (let i = 0; i < len; i++) {
			const [node, index] = queue.shift();

			// 减去这一层的最左节点的索引，防止溢出
			const curIndex = index - startIndex;

			// 记录这一层的最左和最右节点的索引
			if (i == 0) first = curIndex;
			if (i == len - 1) last = curIndex;

			if (node.left) queue.push([node.left, curIndex * 2 + 1]);
			if (node.right) queue.push([node.right, curIndex * 2 + 2]);
		}
		res = Math.max(res, last - first + 1);
	}
	return res;
};