Written by
Wayne
on
on
[Javascript]BFS & DFS
카테고리 설명
정렬되지 않은 이진 트리 전체를 탐색하는 방법에 관한 고찰
1. BFS(넓이 우선 탐색) & DFS(깊이 우선 탐색)
2.BFS(넓이 우선 탐색)
function BFS(root) {
let node = root;
const data = [];
const queue = [];
queue.push(node);
while (queue.length) {
node = queue.shift();
data.push(node);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return data;
}
3. DFS(깊이 우선 탐색)
//proOrder
function proOrder(root) {
const data = [];
function helper(node) {
data.push(node);
if (node.left) helper(node.left);
if (node.right) helper(node.right);
}
helper(root);
return data;
}
function postOrder(root) {
const data = [];
function helper(node) {
if (node.left) helper(node.left);
if (node.right) helper(node.right);
data.push(node);
}
helper(root);
return data;
}
function inOrder(root) {
const data = [];
function helper(node) {
if (node.left) helper(node.left);
data.push(node);
if (node.right) helper(node.right);
}
helper(root);
return data;
}
4. 각각 언제 사용하는가?
공간복잡도 기준, bfs는 폭이 좁고 깊은거, dfs는 폭이 넓고 얕은거에 쓰는게 좋다.
넓고 얕은 곳에 bfs를 사용하면 queue에 들어가있는 값이 많아지고 메모리도 더 많이 소모. 너무 깊은 곳에 dfs를 사용하면 재귀함수가 쌓여서 메모리를 더 많이 소모