TIL

---

오늘 한 일

• 휴식
• leetcode
  • Convert BST to Greater Tree. (medium)

---

문제 풀이

Convert BST to Greater Tree. (medium)

주어진 이진 탐색트리를 우측 부터 좌측 방향으로 누적 값을 가지는 이진 탐색트리로 재구성 하는 문제이다. 누적되는 값은 노드의 레벨보다는 해당 노드의 좌측인지 우측인지가 더 우선신 된다. 따라서 부모 노드보다 부모노드의 좌측 자식이 더 높은 누적 값을 가지게된다.

따라서 주어진 트리 순회를 우측 방향부터 시작하여 현재 누적되는 값을 다음 진행 때 넘겨주는 방식으로 고안하였으며 각 단계 마다 시행되는 방식은 재귀적 방식을 사용하였다.

사용되는 재귀 함수 내에서의 동작은 다음과 같다.

1. 누적할 트리 노드 root 와 현재 누적된 값 v가 주어진다.

2. root 가 null 인지 판별한다 null 이라면 root와 0을 반환 한다. (초기에 주어진 트리노드가 빈 트리 노드일때를 염두에 둔 라인이다. 이후 진행되는 부분에서는 먼저 자식 노드가 null인지를 확인하므로 해당 라인이 사용되는 일은 드믈것으로 생각 된다.)

3. 우선 우측 자식의 노드가 null 인지 확인하고 null이 아니면 우측 노드를 바탕으로 재귀함수를 시행한다. 시행된 결과 노드를 우측 자식 노드로 대체하고(누적 된 결과값을 가진 노드이다.), 현재 누적값을 언어진 누적값으로 교체한다.

4. 현재 노드의 값을 누적 값에 합산하고 합산된 값을 현재 노드의 값으로 변경 한다.

5. 우측 노드와 유사한 방식을 좌측 노드에서도 시행한다.

6. 변경된 트리 노드와 누적 값을 돌려준다.

위 과정이 모든 트리 노드에 대해서 진행되면 최종적으로 누적된 값을 가진 트리노드와 총 누적 값을 얻게 된다.

---

오늘은...

휴식