0662. Maximum Width of Binary Tree

题目信息

题号:

0662

难度:

Medium

主题:

二叉树、层级宽度、完全二叉树位置、空位计入跨度

原题:

LeetCode 0662

重点:

每层宽度从最左非空节点到最右非空节点、两端之间按完整二叉树位置存在的空位也计数、返回所有层最大值

题目重述

给定非空二叉树根节点 root。把树想象为嵌入一棵同深度的完全二叉树,对每一层计算最左侧非空节点与最右侧非空节点之间的完整位置数量,包含二者以及中间的空位置。

返回所有层宽度中的最大值。层外侧、位于最左节点左边或最右节点右边的空位不计入。树中节点数位于 [1, 3000],节点值位于 [-100, 100],答案保证在 32 位有符号整数范围内。

自建示例

中间空位置计入宽度:

输入:root = [1,2,3,4,null,null,7]
输出:4
解释:第三层的节点 4 和 7 位于该层完整布局的两端,中间两个空位置也计入,因此该层宽度为 4。

只有一个节点:

输入:root = [6]
输出:1
解释:根层只有一个非空节点,宽度为 1。