Leetcode 2진 검색 트리 적합성 검사

https://velog.io/@jihyeonjeong11/Codewars-kyu4-%EC%B2%B4%EC%8A%A4-%EA%B8%B0%EC%82%AC%EC%9D%98-%EC%B5%9C%EC%86%8C-%EC%9D%B4%EB%8F%99-%ED%9A%9F%EC%88%98

에서 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의 예시로 적합하다.