98. Validate Binary Search Tree

문제링크: https://leetcode.com/problems/validate-binary-search-tree/

해당 트리가 BST인지 판별하는 문제다.

Solution

Inorder traversal using closure

BST의 특징은 왼쪽노드의 최대 < 중간노드 < 오른쪽노드의 최소 값이라는 것이다. 이는 중위 순회를 했을 경우 점점 증가한다는 점을 시사한다. 따라서 중위 순회를 통해 노드들을 탐색하고 점점 커지는지 확인하는 값을 만들어 클로저로 사용한다면 중위 순회의 노드값이 점점 커지는지 판별할 수 있다.

Algorithm

• temp는 순회를 위해 탐색한 노드의 값이 점점 커지는지 확인하기 위해 사용하는 클로저다. (이 변수는 선언된 렉시컬 스코프를 따르기 때문에 이 함수가 언제 어디서 불려져도 여러개로 나눠지지 않고 같은 변수를 사용하게 된다.)
• 중위 순회를 위해 왼쪽노드를 먼저 판별하고 왼쪽노드가 BST라면 temp에는 왼쪽 노드의 가장 큰 값을 저장하고 있다. 이를 현재 노드와 비교해 BST의 특성을 만족하는지 확인하고 오른쪽 노드를 탐색한다.
• 위 과정을 재귀를 통해 순회하면 중위 순회의 노드값들이 점점 증가하는지 확인할 수 있고 끝까지 순회한다면 BST임을 알 수 있다.

var isValidBST = function(root) {
  // Inorder traversal getting bigger
  // Using closure
  let temp = -Infinity;
  const inorder = (root) => {
    if (!root) return true;
    if (!inorder(root.left)) return false;;
    if (temp >= root.val) return false;
    else temp = root.val;
    if (!inorder(root.right)) return false;
    return true;
  }
  return inorder(root);
};