에서 BFS 너비 우선 알고리즘을 복습한 터라, DFS 깊이 우선 알고리즘을 공부해보고 싶어서 문제를 찾아보았다.
https://leetcode.com/problems/validate-binary-search-tree/
2진 검색 트리란, 상위 노드에서 최대 두 개의 자식을 가지는 2진 트리에 더해서, 한 노드를 기준으로 왼쪽 노드는 작은 값, 오른쪽은 큰 값을 가지는 것을 말한다.
해당 문제는 이진 검색 트리가 적합한 것인가? 를 묻는 것이기 때문에, 위 왼쪽 노드는 작은 값, 오른쪽 노드는 큰 값으로 나누어서 생각하면 쉽게 해결할 수 있다.
var isValidBST = function(root) {
function inOrder(root) {
let visited = [],
current = root;
// 맨 아래 왼쪽 중간, 오른쪽 노드 순으로 넣으면
let traverse = node => {
if (node.left) traverse(node.left);
visited.push(node.val);
if (node.right) traverse(node.right);
};
traverse(current);
return visited;
}
//이진 검색트리이므로 이 숫자들은 오름차순이 되어야만 한다.
const traversed = (inOrder(root));
for(let i = 1; i<traversed.length; i++){
if(traversed[i] <= traversed[i-1]) return false;
};
return true;
};
또한, 한 노드의 맨 자식노드까지 찾아서 거기서부터 연산하므로 DFS의 예시로 적합하다.