98. Validate Binary Search Tree

98. Validate Binary Search Tree

문제

이진 트리의 루트가 주어지면 유효한 이진 검색 트리(BST)인지 확인한다.
1. 왼쪽 자식 노드는 부모 노드의 값보다 작아야 한다.
2. 오른쪽 자식 노드는 부모 노드의 값보다 커야 한다.
3. 왼쪽 및 오른쪽 하위 서브트리도 모두 이진 검색 트리여야 한다.

테스트 케이스

Input: root = [2,1,3]
Output: true

풀이

재귀적으로 탐색하기 전에 왼쪽 자식 노드는 부모 노드(max)보다 크지 않다(작다). 오른쪽 자식 노드는 부모 노드(min)보다 작지 않다(크다). 재귀 함수를 호출할 때 서브트리의 루트 노드를 min 또는 max로 업데이트해 준다. (max | min) !== null은 왼쪽인지 오른쪽인지 확인하기 위해 사용한다.

/**
 * @param {TreeNode} root
 * @return {boolean}
 */

var isValidBST = function(root) {
  return checkIfValid(root, null, null);
};

var checkIfValid = function(root, min, max) {
  // 말단 노드까지 검사가 끝났다면 true를 반환
  if (root === null) return true;

  // 오른쪽 노드를 탐색할 때 min를 업데이트하면서 
  // min보다 큰지 확인 
  if (min !== null && root.val <= min) {
    return false;
  }

  // 왼쪽 노드를 탐색할 때 max를 업데이트하면서 
  // max보다 작은지 확인
  if (max !== null && root.val >= max) {
    return false;
  }

  return checkIfValid(root.left, min, root.val) && checkIfValid(root.right, root.val, max);
}