책너두 (코딩 인터뷰 완전분석) 16일차 (4.1 ~ 4.6)

메모

면접 문제

4.1 노드 사이의 경로

• 방향 그래프가 주어졌을 때 두 노드 사이에 경로가 존재하는지 확인하는 알고리즘을 작성하라.

4.2 최소 트리

• 오름차순으로 정렬된 배열이 있따. 이 배열 안에 들어 있는 원소는 정수이며 중복된 값이 없다고 했을 때 높이가 최소가 되는 이진 탐색 트리를 만드는 알고리즘을 작성하라.

4.3 깊이의 리스트

• 이진 트리가 주어졌을 때 같은 깊이에 있는 노드를 연결리스트로 연결해 주는 알고리즘을 설계하라. 즉, 트리의 깊이가 D라면 D개의 연결리스트를 만들어야 한다.

4.4 균형 확인

• 이진 트리가 균형 잡혀있는지 확인하는 함수를 작성하라. 이 문제에서 균형 잡힌 트리란 모든 노드에 대해서 왼쪽 부분 트리의 높이와 오른쪽 부분 트리의 높이의 차이가 최대 하나인 트리를 의미한다.

4.5 BST 검증

• 주어진 이진 트리가 이진 탐색 트리인지 확인하는 함수를 작성하라.

4.6 후속자

• 이진 탐색 트리에서 주어진 노드의 ‘다음’ 노드(중위 후속자(in-order successor))를 찾는 알고리즘을 작성하라. 각 노드에는 부모 노드를 가리키는 링크가 존재한다고 가정하자.