LeetCode 98 - Validate Binary Search Tree (Medium)

문제

LeetCode - 98번

풀이 과정

입력으로 주어진 트리가 이진 검색 트리 의 요구 사항에 맞는 구조를 가지고 있는지 판단하는 문제입니다.

이진 검색 트리 는 루트 노드가 왼쪽 서브트리의 모든 노드보다 커야하고 오른쪽 서브트리의 모든 노드보다 작아야합니다.
따라서 minMax 라는 함수를 통해 DFS 를 수행하며 현재 루트 노드를 기준으로
해당 서브트리의 가장 작은 값과 가장 큰 값을 반환하도록 합니다.

그런데 다 풀고나서 다른 사람들의 풀이법을 보니 그냥 중위 순회 를 한 다음
오름차순으로 되어있는지 확인하는 방법이 더 구현하기 쉽고 명확한 거 같습니다.

코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  let satisfied = true;

  function minMax(root) {
    if (!root) return [null, null];

    const [leftMin, leftMax] = minMax(root.left);
    const [rightMin, rightMax] = minMax(root.right);

    if (leftMax && leftMax >= root.val) {
      satisfied = false;
    }

    if (rightMin && root.val >= rightMin) {
      satisfied = false;
    }

    const minValue = leftMin || root.val;
    const maxValue = rightMax || root.val;

    return [minValue, maxValue];
  }

  minMax(root);

  return satisfied;
};