개발하는 두더지

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

알고리즘

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

덜지 2018. 9. 15. 01:24

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


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


Comments