문제

• 
• 시간 제한: 1초
• 메모리 제한: 256MB

Problem Analysis

어떤 순서로 출력하든 간에, 먼저 tree를 갖고 있어야 한다. 이때, 예를 들어, 한 node의 값이 30이고 구간이 [20, 50]이라면, right-subtree는 구간이 [31, 50]이고, left-subtree는 구간이 [20, 29]이라는 점을 이용하면 된다.

Algorithm

pre-order는 root, Left, Right 순서이다.

Recursive call을 통해 해결한다.
1. 현재 node의 left child를 결정한다.
2. 현재 node의 right child를 결정한다.

위 순서로 결정하되, 매번 다음의 조건에 따라 결정한다.

• 현재 조사 중인 값이, 현재 node의 하위 구간에 수용할 수 있으면, L-child 또는 R-child로 할당하고 recursive call을 한다.
• 현재 조사 중인 값이, 현재 node의 하위 구간에 수용할 수 없으면, nullptr로 설정.

Data Structure

• struct node:

	- val: 현재 node의 value
    - l, r: 현재 node의 범위   
    - lc, rc: 현재 node의 children

결과

Other

시간 복잡도는 O(N) 이다.