[리트코드 102] Binary Tree Level Order Traversal

문제는 아래와 같이 주어집니다.

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

depth 1, 2와 같이 레벨로 구하는 것이기 때문에 너비 우선 탐색 (BFS, Breadth First Search) 와 같은 개념으로 풀 수 있습니다.

[필수 개념]

1. 너비 우선 탐색(BFS)

 깊이 우선 탐색(DFS)과 달리 스택(Stack)을 이용하지 않고 큐(Queue)를 이용하며 트리나 그래프에서 탐색에 사용되는 알고리즘

2. 자바 Queue, LinkedList 사용방법

 - offer()  Queue에 삽입

 - poll()  Queue에서 제거하며 읽기/반환

 - peek()  Queue에서 제거하지 않고 읽기/반환

스택은 메소드 이름이 다릅니다.

 - push()  Stack에 삽입

 - pop()  Stack에서 제거하며 읽기/반환

 - peek()  Stack에서 제거하지 않고 읽기/반환

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

class Solution {

public List<List<Integer>> levelOrder(TreeNode root) {

List<List<Integer>> ret = new ArrayList<>();

if(root == null) return ret;

Queue<TreeNode> q = new LinkedList<>();

q.offer(root);

while(!q.isEmpty()) {

List<Integer> level = new ArrayList<>();

int size = q.size();

for(int i = 0; i < size; i++) {

TreeNode node = q.poll();

level.add(node.val);

if(node.left != null) q.offer(node.left);

if(node.right != null) q.offer(node.right);

}

ret.add(level);

}

return ret;

}

}

참고

리트코드 102

너비우선탐색 알고리즘 설명

자바 Queue, LinkedList 설명

면접코딩 이진트리 107