分享
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。
每一层的宽度被定义为两个端点(该层最左和最右的非空节点,两端点间的null节点也计入长度)之间的长度。
示例 1:
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: 4
解释: 最大值出现在树的第 3 层,宽度为 4 (5,3,null,9)。
示例 2:
输入:
1
/
3
/ \
5 3
输出: 2
解释: 最大值出现在树的第 3 层,宽度为 2 (5,3)。
示例 3:
输入:
1
/ \
3 2
/
5
输出: 2
解释: 最大值出现在树的第 2 层,宽度为 2 (3,2)。
示例 4:
输入:
1
/ \
3 2
/ \
5 9
/ \
6 7
输出: 8
解释: 最大值出现在树的第 4 层,宽度为 8 (6,null,null,null,null,null,null,7)。
注意: 答案在32位有符号整数的表示范围内。
func getHorizontalMaxNum(root *Node) int {
var max int
if nil == root {
return max
}
nodeSlice := make([]*Node, 0)
nodeSlice = append(nodeSlice, root)
for {
length := len(nodeSlice)
if 0 == length {
break
}
if max < length {
max = length
}
tmpNodeSlice := make([]*Node, 0)
for i := 0; i < length; i++ {
tmpNode := nodeSlice[i]
if tmpNode == nil {
tmpNodeSlice = append(tmpNodeSlice, nil, nil)
} else {
tmpNodeSlice = append(tmpNodeSlice, tmpNode.Left, tmpNode.Right)
}
}
i := 0
for {
if i >= len(tmpNodeSlice) || nil != tmpNodeSlice[i] {
break
}
i++
}
tmpNodeSlice = tmpNodeSlice[i:]
i = len(tmpNodeSlice) - 1
for {
if i < 0 || nil != tmpNodeSlice[i] {
break
}
i--
}
tmpNodeSlice = tmpNodeSlice[:i+1]
nodeSlice = tmpNodeSlice
}
return max
}
有疑问加站长微信联系(非本文作者))
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信1048 次点击
上一篇:go语言中的for循环
下一篇:Go数据类型整理
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传