이진트리의 최대 넓이

이진트리의 최대 넓이는 각 level에서의 넓이 중 가장 큰 값으로 정의한다.

예제 트리에서 각 레벨의 넓이는

• Level 1 = 1
• Level 2 = 2
• Level 3 = 3
• Level 4 = 4
• Level 5 = 3

이므로, 트리의 최대 넓이는 4이다.

Level-order 탐색을 활용하여 각 level에서의 width를 구하고, 이들 중 최대값을 구하는 방식으로 구현한다.

func GetMaxWidth(root *Node) int {

  if root == nil {

    return 0

  }

  maxWidth := 0

  Q1 := []*Node{}

  Q2 := []*Node{}

  Q2 = append(Q2, root)

  for len(Q2) > 0 {

    Q1, Q2 = Q2, Q1

    Q2 = Q2[:0]

    size := len(Q1)

    if maxWidth < size {

      maxWidth = size

    }

    for _, node := range Q1 {

      if node.Left != nil {

        Q2 = append(Q2, node.Left)

      }

      if node.Right != nil {

        Q2 = append(Q2, node.Right)

      }

    }

  }

  return maxWidth

}