JavaScript BST 연습: 닫힌 구간의 중복 키 보고서

한 파일로 실행하는 전체 정답

'use strict';

function checkKey(key) {
  if (!Number.isSafeInteger(key)) throw new TypeError('key must be a safe integer');
}

function rangeValues(root, low, high) {
  checkKey(low);
  checkKey(high);
  const result = [];
  if (low > high) return result;
  const stack = [];
  let current = root;
  while (current != null || stack.length > 0) {
    while (current != null) {
      if (current.key < low) {
        current = current.right;
      } else {
        stack.push(current);
        current = current.left;
      }
    }
    if (stack.length === 0) break;
    current = stack.pop();
    if (current.key > high) break;
    for (let copy = 0; copy < current.count; copy += 1) {
      result.push(current.key);
    }
    current = current.right;
  }
  return result;
}


function solve({ root, low, high }) {
  return rangeValues(root, low, high);
}

module.exports = { solve };

if (require.main === module) {
  const fs = require('node:fs');
  const input = JSON.parse(fs.readFileSync(0, 'utf8').replace(/^\uFEFF/, ''));
  process.stdout.write(JSON.stringify(solve(input)) + '\n');
}

정답 해설: 순서가 생략을 정당화합니다

내부 반복에서 key < low인 노드는 스택에 저장하지 않고 오른쪽으로 넘어갑니다. 그 노드의 왼쪽까지 방문할 필요가 없기 때문입니다. 나머지는 스택에 쌓고 왼쪽으로 내려가 아직 출력하지 않은 작은 키를 먼저 처리합니다.

스택에서 꺼낸 키는 low 이상입니다. 그 키가 high를 넘으면 이후 중위 방문도 더 큰 키뿐이라 break로 전체 반복을 끝낼 수 있습니다. 범위 안이면 count만큼 결과에 추가하고 오른쪽 부분 트리로 이동합니다. 입력의 연결이나 count를 고치지 않는 읽기 전용 연산입니다.

예시에서는 왼쪽 키 7의 count가 2이고 키 14의 count가 3입니다. 같은 숫자를 여러 번 출력하는 것은 중복 방문 오류가 아니라 문제에서 요구한 확장입니다. low=high=14라면 14 세 개만 출력하고 low=15,high=14라면 탐색 없이 빈 결과입니다.

복잡도

h는 높이, k는 실제 출력 개수입니다. 유효한 BST에서 범위 안 노드와 두 경계로 가는 경로만 방문하므로 시간은 O(h+k+1), 최악 O(U+k)입니다. 보조 스택은 O(h+1), 결과는 O(k)입니다. 표준 입력 JSON 트리까지 포함한 전체 프로그램 공간은 O(U+k)이며, 트리 균형은 보장하지 않으므로 h를 무조건 log U로 바꾸면 안 됩니다.

이 문제는 완성된 트리를 받으므로 삽입으로 구축하는 비용은 없습니다. values 배열을 BST에 하나씩 넣는 별도 입력 설계를 택하면 정렬된 입력에서 구축만 O(U²)이 될 수 있습니다. 입력 형식이 달라지면 같은 범위 함수라도 프로그램 전체 복잡도가 달라집니다.

직접 확인할 경계

빈 root, low > high, 모든 키보다 낮거나 높은 범위, 한 키만 포함하는 범위, 중복 횟수가 큰 노드, 편향 트리를 확인하세요. 테스트에서는 BST에 넣은 원래 다중집합을 filter 후 sort한 결과와 비교하면 가지치기 구현과 독립적으로 정답을 확인할 수 있습니다.