문제

• 
• 시간 제한: 2초
• 메모리 제한: 128MB

Problem Analysis

먼저, 각 node의 위치를 구해야 한다. 이는 (왼쪽 자손의 수) + (현 node의 범위 왼쪽 끝)으로 구할 수 있다. In-Order DFS를 이용하면 된다.

Algorithm

(l, .., ) 구간에 존재할 수 있는 현재 node의 위치를 다음과 같이 구한다.

• DFS를 하여, 왼쪽 자손의 수를 구한다.
• 현재 node의 위치, idx를 정한다.
• (idx+1, ..., ..) 구간에 존재할 수 있는 오른쪽 자손으로 DFS.
• 자신을 포함한 sub-tree nodes의 수를 return

Data Structure

• rangeOfEachLevel[][2]: 각 level에서의 좌우 column 범위 저장
• tree[n][2]: 각 node의 l, r child의 번호 저장

결과

Other

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