给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(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
}
有疑问加站长微信联系(非本文作者))