[LeetCode] Validate Binary Search Tree

🧑‍💻 언어 및 제출 결과

• 사용 언어: TypeScript
• 통과 여부: ✅

🧠 풀이 설명

노드의 왼쪽 서브트리는 작은 값이여야하고, 오른쪽 서브트리는 큰값이여야 한다고 합니다 root는 탐색중인 노드라고 생각했을 때 재귀를 사용하면 쉽게 풀 수 있을 거 같아 재귀를 사용했습니다.

첫 번째 시도

function isValidBST(root: TreeNode | null): boolean {
  if (!root || !root.left || !root.right) return false;

  if (root.val < root.left!.val) return false;
  if (root.val > root.right!.val) return false;

  return true;
}

왼쪽 서브트리는 작은 값, 오른쪽 서브트리는 큰값이여야 하기 때문에 간단한 조건문으로 재귀를 써서 풀어보려 했는데 애초에 조건을 잘못 생각 했던 것 같습니다 [0]인 케이스에서 true를 return 해야 되는데 false를 return 실패하고, 여러가지 조건을 추가해서 넣어봤지만 여러 엣지 케이스에서 걸려서 실패했습니다 음 이건 문제에 없었는데... BST 자체에 개념을 처음 봐서 BST 먼저 학습을 한 후에 다시 풀어봤습니다. 학습한 결과 우선 중복된 키는 허용하지 않는다는 점을 안된다고 합니다. 왜 문제엔 안 적어 놨지 기다 등등 생각보다 신경 쓸게 많았습니다.

---

두 번째 시도

/**
 *
 * @param root 현재 노드
 * @param min 왼쪽 서브트리의 최소값
 * @param max 오른쪽 서브트리의 최대값
 * @returns 현재 노드가 BST인지 여부
 */
function isValidBST(root: TreeNode | null, min: number = -Math.pow(2, 31) - 1, max: number = Math.pow(2, 31)): boolean {
  if (!root) return true;

  if (root.val <= min || root.val >= max) return false;

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

최소 값과 최대 값을 넘겨주면서 재귀를 활용해서 풀었습니다. 기저 조건은 root가 null일 때, 리프 노드일 때 true를 return 하게 조건을 줬고, 범위는 제약 범위가 -2³¹ ≤ Node.val ≤ 2³¹ - 1 이기 때문에 제약 조건보다 1씩 더 크고 작게 잡아줬습니다
왼쪽 자식은 현재 노드보다 작아야 하니까, max를 root.val로 제한하고 (탐색 노드, min, 현재 노드 값)
오른쪽 자식은 현재 노드보다 커야 하니까, min을 root.val로 제한하고 (탐색 노드, 현재 노드 값, max)
그러므로 이 조건이 아닐 경우엔 false를 return 하게 조건을 줬tmqslek.

왼쪽과 오른쪽 서브트리 모두 유효한 BST여야 하므로 AND 연산자로 연결해서 둘 다 true일 때만 전체가 유효한 BST가 되도록 해서 통과 했습니다.

📊 시간/공간 복잡도

✅ 어떠한 근거로 시간/공간 복잡도가 이렇게 나왔는지 설명해주세요.

• 시간 복잡도: O(n) - 모든 노드를 한 번씩 방문
• 공간 복잡도: O(n) - 재귀 호출 스택에 따른 깊이

⚡️ 풀이의 속도와 메모리 등을 캡쳐해서 올려주세요.