二叉树的最大宽度

[编程题]二叉树的最大宽度

热度指数：2343 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉树，请你求出此二叉树的最大宽度。

本题中树第 i 层的宽度定义为：第 i 层最左边的节点到最右边之间的距离，中间空节点也计入距离。

例如：

本树中第 1 层只有一个节点，故第 1 层宽度是 1 ，第二层最左侧到最右侧的距离是 2 ，所以宽度是 2 ，第三层最左侧 4 到最右侧 5 距离是 4 ，故宽度是 4，此树最大宽度是 4。

示例1

输入

{1,2,3,4,#,4,5}

输出

说明

如题面图

示例2

输入

{1}

输出

示例3

输入

{1,2,3,4,#,4,5,6,#,1}

输出

说明

倒数第二层的宽度为5

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

空中转体一周半

发表于 2022-05-24 11:13:23

思路：本题乍一看可以用层序遍历？但是涉及到空节点的问题，层序遍历存在诸多麻烦，因此可以利用二叉树的特性：左叶子节点的序号为根节点的两倍，右叶子节点的序号为根节点的2倍加1.利用这个性质，我们把每一层的最左节点的序号加入一个map中（这个动作只进行一次即可），以后每次遍历到该层的时候，刷新该层的最大节展开全文

B612_2024

发表于 2021-12-06 12:40:35

* struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * 展开全文

fred-coder

发表于 2021-12-12 17:37:50

根据二插树的节点间的位置关系, left_child = root * 2, right_child = root * 2 + 1 利用层序遍历，进行判断处理 class Solution: def widthOfBinaryTree(self , root: TreeNode) -> 展开全文

代码界的小白

发表于 2022-03-07 22:27:50

二叉树的最大宽度给定一个二叉树，请你求出此二叉树的最大宽度。本题中树第 i 层的宽度定义为：第 i 层最左边的节点到最右边之间的距离，中间空节点也计入距离。方法一：广度搜索具体方法给每个节点设置一个索引index，如果向左走，就将2∗index2*index 2∗index左子树存起来，如展开全文

小步惊惊

发表于 2022-05-02 15:20:33

先获取树的最大深度，然后按照深度把原树改为一棵完全二叉树，添加上去的节点是一个特殊值的标记节点，然后再进行层序遍历获取每一层的节点值，再对每一层的节点进行获取，把最左边和最右边的是特殊值的树节点去掉，最终得到的就是该层的实际宽度，然后遍历得到最大宽度即可。 import java.util.*; / 展开全文