Allergens Fish Streamline Icon: https://streamlinehq.com

98. Validate Binary Search Tree

4 min read

문제

https://leetcode.com/problems/validate-binary-search-tree/

root가 주어졌을 때 유효한 BST인지 판단하는 문제

유효한 BST란?

  • 현재 노드의 왼쪽 서브트리는 모두 현재 노드보다 작음
  • 현재 노드의 오른쪽 서브트리는 모두 현재 노드보다 큼
  • 각 서브트리는 모두 BST여야 함

풀이 - 전위순회

아이디어

현재 노드가 root인 tree의 BST 여부는 왼쪽 서브트리가 BST인지와 오른쪽 서브트리가 BST인지를 확인해서 판단할 수 있다. 간단한 내용이지만,, 그림으로 그려보면 아래와 같다.

이 때 중요한 것은 각 서브트리의 모든 노드들이 root 보다 작거나 크거나 해야 한다는 것이다. 단순히 서브트리의 root 노드만 확인하면 안되는 이유는 다음과 같은 케이스에서 확인할 수 있다.

6을 루트로 하는 오른쪽 서브트리는 왼쪽에 3, 오른쪽에 7로 BST의 요건을 달성했지만, 3은 전체 루트 노드인 5보다 작은 값인데 오른쪽 서브트리에 있으므로 전체 트리는 유효한 BST가 아니게 된다.

따라서 BST 여부를 판단할 때 노드들의 범위까지도 함께 고려해줘야 한다.

  • 왼쪽 자식 트리의 범위는 “하한”은 계속 유지되고 (음의 무한대), “상한”은 부모 노드의 값으로 업데이트된다.
  • 오른쪽 자식 트리의 범위는 “상한”은 계속 유지되고 (양의 무한대), “하한”은 부모 노드의 값으로 업데이트된다.

코드

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}
 
function isValidBST(root: TreeNode | null): boolean {
  // 노드가 하나만 있는 경우를 먼저 처리해줬다.
  if (root === null || (root.left === null && root.right === null)) {
    return true;
  }
 
  function checkSubTree(
    currNode: TreeNode | null,
    min: number,
    max: number
  ): boolean {
    if (currNode === null) {
      return true;
    }
    if (currNode.val <= min || currNode.val >= max) {
      return false;
    }
 
    return (
      checkSubTree(currNode.left, min, currNode.val) &&
      checkSubTree(currNode.right, currNode.val, max)
    );
  }
 
  return checkSubTree(root, -Infinity, Infinity);
}

시간 / 공간 복잡도

시간 복잡도는 모든 노드를 한번씩 확인하므로 **O(n)**이 된다.

재귀적으로 돌아가는 코드이기 때문에 공간 복잡도는 재귀 콜 스택에 의해 결정된다! 재귀 호출은 양쪽 트리로 쪼개져서 호출되기 때문에 (왼쪽 다 하고 오른쪽 검사) 콜 스택의 최대 깊이는 트리의 최대 깊이가 된다. 최악의 경우 (왼쪽이나 오른쪽 노드만 있는 연결 리스트 형태의 트리) 깊이가 n이 되므로 콜 스택의 깊이가 n이 되어 **공간 복잡도는 O(n)**이 된다.

그래프 뷰