98. Validate Binary Search Tree

https://leetcode.com/problems/validate-binary-search-tree/

위 문제를 재귀로 풀어보자

이진 탐색 트리의 기본적인 규칙은 위와 같다. 하나의 노드를 기준으로 봤을 때는 매우 심플하다. 하지만, 확장시켜서 생각해본다면

G, B, E 각각의 노드에서 요구되는 규칙은 '노란색'과 같다. 이는 이전에 언급한 규칙과 동일하다. 그리고 이 규칙으로 인해서 '빨간색' 규칙이 자연스럽게 만족되기 때문에, 별도의 확인 과정을 거치지 않아도 된다. 진짜 문제는 '파란색' 규칙들부터 시작된다. 자식의 자식 노드는 부모의 부모 노드에 대한 정보를 알아야 한다. 하지만 이게 끝이 아니다.

위와 같이, 특정 방향으로의 모든 자식 노드들은, 부모 노드뿐만 아니라 특정 노드와 값 비교를 해야 한다. 여기서 특정 방향이라 함은 아래의 '보라색' 화살표와 같다.

본 문제 풀이를 위해서는 기본적으로 '재귀'를 이용한다. 이진 트리에서 재귀라 함은 보통 아래와 같이 구성이 된다.

return f(node.left) & f(node.right);

위 그림을 보면, 두 가지 보라색 화살표가 제시되어 있다. 하나는 왼쪽으로 내려가기만 하는 화살표, 하나는 오른쪽으로 한번 꺾은 후, 왼쪽으로 내려가는 화살표. 이 두가지는 규칙이 다르다는 점에서 구분되어야 한다.

(1) 왼쪽으로 내려가는 화살표가 지나가는 노드들의 규칙은, 부모 노드보다는 작아야 한다는 것이다.
(2) 하지만 다른 화살표는, 부모 노드보다 작아야 한다 & 특정 노드보다 커야한다는 규칙이 존재한다.

그래서 C노드의 왼쪽 자식들은 모두, A노드에 대한 정보가 필요하다. 상위 노드에 대한 정보를 전달하기 위해, 매개 변수를 추가하게 되는데, min과 max에 대한 정보를 넣는다.

return f(node.left, min, max) & f(node.right, min, max);

재귀를 쉽게 풀기 위해서 함수가 실행된 이후의 상황을 상상한다. 현재 C가 실행되었다고 하자. C는 A에 대한 정보를 가지고 있고, 이를 왼쪽 자식노드에게 전달할 것이다. 이때 매개 변수 min을 그대로 전달하면 된다. 이때 max에는 무엇을 전달하면 될까? 자기 자신을 전달하면 된다.

그렇게 되면 F가 실행되었을 때 min(A) < F < max(C) 조건을 확인할 수 있게 된다.
또한 F입장에서는 M에게 max로 C에 대한 정보를 전달할 수 있게 된다.

C입장에서 F에 전달되는 매개변수를 다시 정리해보면, 아래와 같다.

f(node.left, min(=A), max(=C))

이 조건은 앞선 사진에서 두 번째 화살표의 두 번째 조건(2)에 해당한다. (1)과 (2)는 다른 조건이지만, (1)은 (2)에 포함되어 있으므로, 모든 노드에서 왼쪽 자식을 확인할 때 문제 없이 적용이 된다.

지금까지 왼쪽 방향에 대해서만 확인했다. 오른쪽 방향에 대해서는 스스로 구성해보자.