每日一题：LeetCode-662. 二叉树最大宽度

作者：半亩房顶

2023-12-25
北京
本文字数：1309 字
阅读完需：约 4 分钟

刷题使我快乐，满脸开心.jpg

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-width-of-binary-tree/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你一棵二叉树的根节点 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的心智负担是比较小的，而且复杂度也不会太差
带着父节点下标这个问题，构造一个包含节点和对应下标值的结构体就好了~

代码也基本就出来了。老样子，细节在代码注释

代码

type TreeNodeIndex struct {    Node  *TreeNode    Index int}
func widthOfBinaryTree(root *TreeNode) int {    nodeIdxs := []*TreeNodeIndex{{root, 0}}    temp := make([]*TreeNodeIndex, 0)    res := 0    // 遍历完整棵树的条件    for len(nodeIdxs) != 0 {        // 按这里代码的顺序，左节点在前，右节点在后，所以用后面的减前面的        // 提交时候才发现golang语言里，这个max函数是默认提供的        res = max(nodeIdxs[len(nodeIdxs)-1].Index-nodeIdxs[0].Index+1, res)        for _, nodeIdx := range nodeIdxs {            // 优先放入左节点            if nodeIdx.Node.Left != nil {                temp = append(temp, &TreeNodeIndex{                    Node:  nodeIdx.Node.Left,                    // 左右子节点下标均可计算得出                    Index: 2*nodeIdx.Index + 1,                })            }            if nodeIdx.Node.Right != nil {                temp = append(temp, &TreeNodeIndex{                    Node:  nodeIdx.Node.Right,                    Index: 2*nodeIdx.Index + 2,                })            }        }        // 更新每层节点列表        nodeIdxs = temp        temp = nil    }    return res}