[leetcode] [javascript] Binary Tree Level Order Traversal

rud285·2020년 9월 15일
0

[알고리즘]

목록 보기
17/23
var levelOrder = function (root) {
  if (root === null) {
    return []
  }

  let result = []
//   [[1],[2,3],[4,5,6]]
// 트리의 노드를 큐에 저장을 해놓음 
// 왼쪽 자식있으면 큐에넣고, 오른쪽 자식 있으면 큐에넣어 
// 자식확인했으면 큐에넣은 것을 빼서 결과배열에 push 
// 맨 먼저 1이 들어가고 [1] 1의 자식인 2,3 이 큐에들어가고 [1,2,3]
// 1이 빠져나오고 [2,3]
// 2의 자식인 4가 큐에들어가고 [2,3,4]
// 2확인 끝났으니 임시 창고 (numbers) 에 넣음 numbers=[2]
// 3 자식 5,6 큐에 넣음 [3,4,5,6]
// 3을 임시창고에 넣고  numbers [2,3]
// 임시창고를 결과배열에 push [[1],[2,3]]
  let queue = []
  queue.push(root)
  while (queue.length > 0) {
    let temp = [] // 임시창고 자식노드들이 담길창고 
    // queue 의 길이가 계속변화하는데 
    // 자식노드들의 갯수만큼 queue에 넣는 것을 반복하기 위함 
    let tempSize = queue.length

    while (tempSize > 0) {
      let currentNode = queue.shift()

      if (currentNode.left) {
        queue.push(currentNode.left)
      }

      if (currentNode.right) {
        queue.push(currentNode.right)
      }

      temp.push(currentNode.val)

      tempSize--
    }

    result.push(temp)
  }
  return result
}

0개의 댓글