Skip to content

Instantly share code, notes, and snippets.

@alldroll
Created July 9, 2020 17:20
Show Gist options
  • Save alldroll/bd11c0d38712e336c91dfea3ccd2a1d3 to your computer and use it in GitHub Desktop.
Save alldroll/bd11c0d38712e336c91dfea3ccd2a1d3 to your computer and use it in GitHub Desktop.
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type LevelNode struct {
node *TreeNode
level int
order int
}
func widthOfBinaryTree(root *TreeNode) int {
if root == nil {
return 0
}
queue := []*LevelNode{{
node: root,
level: 0,
order: 0,
}}
var prevItem *LevelNode
maxWidth := 0
for len(queue) > 0 {
item := queue[0]
queue = queue[1:]
if prevItem == nil || prevItem.level != item.level {
prevItem = item
}
maxWidth = max(maxWidth, item.order - prevItem.order + 1)
if item.node.Left != nil {
queue = append(queue, &LevelNode{
node: item.node.Left,
level: item.level + 1,
order: 2 * item.order + 1,
})
}
if item.node.Right != nil {
queue = append(queue, &LevelNode{
node: item.node.Right,
level: item.level + 1,
order: 2 * item.order + 2,
})
}
}
return maxWidth
}
func max(a, b int) int {
if a < b {
return b
}
return a
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment