이진 검색 트리 솔루션

[1. 개요]

자료 구조 구현

• 이진 트리는 그 특성 상 배열을 이용하여 구현한다.
• index 0 은 사용하지 않고, index 1 을 루트로 사용한다.
• leaf node 는 왼쪽 노드가 maxNode 보다 큰 경우이다.
  => 왼쪽 노드가 없으면 오른쪽 노드도 당연히 없다.
  => 보통 노드 개수가 문제에 주어진다.
  (완전 이진 트리가 아닌 이상, 마지막 노드 id 를 유추 할 수 없으므로?)
•  

완전 이진 트리

• 모든 레벨에 노드가 가득찬 이진 트리이다.
• 트리의 깊이가 K 일 때, 노드의 개수가 2^K-1 개를 갖는다.
• maxNode id 는 2^k 이다.
  => k == 2, 트리에 존재 할 수 있는 노드 id 는 1, 2, 3
  => maxNode == 4
• 각 레벨 별 노드 id 범위를 쉽게 구할 수 있다.
  => from: (1 << (k-1))
  => to: (1 << k)
  => 노드 id 범위: [from, to)
•  

재귀 함수

• 이진 트리역시 트리이므로, 트리의 재귀적인 특성을 이용하도록 한다.

---

[2. 예제]

• https://testkernelv2.tistory.com/472
• b
• c
• d
• e
• f
• g