의식이 흐르는대로 해보는 프로그래밍

목차접근Easy난이도라는데, 고민을 많이 꽤 했던 것 같다. Grind 75를 따라가면서, 릿코드 문제를 풀어보고 있는 도중에 접했다. Binary Tree의 지름을 구하는 문제이다. 여기서 Diameter(지름)의 의미는 트리에 존재하는 두 노드간의 가장 긴 거리를 의미한다. root를 거칠수도, 거치지 않을 수도 있다. 처음 접근은 정말 단순하게 생각했던 것 같다. 그냥 root의 left, right의 가장 긴 깊이를 구해서 더하면 끝 아닌가? 생각했다. 왜냐하면 가장 긴 거리가 나오려면, 무조건 root 노드를 지나가야한다고 생각했기 때문이다.근데 엄청난 예제가 등장했다...두둥  이 트리는 root를 거치지 않고서, right노드의 하위노드간에서 diameter가 등장한다.(-1 -> -2)그래..

목차 접근 `n`개의 정점을 가는 이진 트리의 정점에서 1 ~ n까지 중복 없이 번호가 매겨져 있다. 이런 이진 트리에서 인오더(중위순회)와 포스트오더(후위순회)가 주어졌을 때, 프리오더(전위순회)를 구하는 문제다. 정말 많이 틀리고, 시간이 들었다. 여러 개선점에 대해서 생각해보는 시간이었다. 먼저 기본적인 접근에 대해서 생각해보자. 중위순회는 이진트리를 Left - Mid - Right 순으로 탐색을 진행한다. 후위순회는 이진트리를 Left - Right - Mid 순으로 탐색을 진행한다. 그럼 맨 처음 주어진 각각의 순회의 결과에서 후위순회의 마지막 결과값이 처음 트리의 Mid의 값이라는 것을 알 수 있다. 그럼 아래와 같으 과정을 거치면, 트리를 재귀적으로 분해해나갈 수 있다. 위에서 구한 Mid..

접근 이진 탐색 트리의 전위 순회 결과만을 이용해서, 후위 순회 결과를 복원해내는 문제이다. 이진 탐색 트리의 전위, 중위 순회결과를 이용해서 트리를 복원해내는 방법이 있는데, 그 방법을 차용해서 해결했다. 해결 전위, 중위 순회 결과만이 있다면, 이진 탐색 트리는 복원이 가능하다. 전위 순회 결과는 항상 맨 처음의 값이 루트 노드이다. 중위 순회 결과는 `Left - Root - Right` 순서이기에, 특정 노드 기준으로 왼쪽 부분결과는 Root보다 작은 값들이고, 오른쪽 부분 결과는 큰 값들이다. 이 두가지 성질을 이용한다면, 이진 탐색 트리를 복원해낼 수 있다. 하지만 우리는 중위 순회 결과가 없기에, 중위 순회 결과를 만들어내야한다. 그냥 그건 간단하다. Root Node보다 작은 값들을 찾아서..