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);
}