서브트리의 개념을 이용하면 트리의 높이를 재귀적으로 정의할 수 있다. 루트의 각 자식들을 루트로 하는 서브트리들의 높이를 각각 재귀 호출을 통해 계산한다. 그러면 전체 트리의 높이는 그중 최대치에 1을 더한 값이 된다.
코드 21.3 순회를 이용해 트리의 높이를 계산하기
// root를 루트로 하는 트리의 높이를 구한다.
int height(TreeNode* root) {
int h = 0;
for (int i = 0; i < root->children.size(); ++i)
h = max(h, 1 + height(root->children[i]));
return h;
}
자손이 없는 경우의 높이가 0이라는 것에 유의합시다. 트리의 순회에는 얼마의 시간이 들까요? 트리에 n개의 노드가 있다고 하면 이들을 모두 순회하기 위해서는 O(n)의 시간이 들어야 정상이다.
트리 순회 순서 변경(TRAVERSAL)
- 전위 순회(preorder traverse)
- 중위 순회(inorder traverse)
-
후위 순회(postorder traverse)
printPostOrder(preorder[], inorder[]) = 트리의 전위 순회 preorder[]와 중위 순회 inrorder[]가 주어질 때, 후위 순회 순서를 출력한다.
가장 먼저 깨달아야 하는 것은 주어진 트리의 루트는 전위 순회에서 가장 먼저 방문으로 preorder[0]이 루트의 번호라는 점입니다. 루트의 번호 root를 찾았으면 inorder[]에서 root를 찾아 봅시다. 중위 순회 결과에서 루트보다 먼저 방문된 노드들은 왼쪽 서브트리에, 늦게 방문된 노드들은 오른쪽 서브트리에 있습니다. 따라서 inorder[]에서 root가 어디 있는지 찾으면 각 서브트리의 크기 L, R을 알 수 있습니다. 그러고 나면 preorder[]와 inorder[]를 적절히 잘라 왼쪽 서브트리의 방문 순서, 오른쪽 서브트리의 방문 순서로 나눌 수 있습니다. 따라서 각 서브트리를 후위 순회한 결과를 재귀 호출을 이용해 출력하고, 마지막으로 루트의 번호를 출력하면 됩니다.
코드 21.4 트리 순회 순서 변경 문제를 해결하는 재귀 호출 코드
vector<int> slice(const vector<int>& v, int a, int b) {
return vector<int>(v.begin() + a, v.begin() + b);
}
// 트리의 전위탐색 결과와 중위탐색 결과가 주어질 때 후위탐색 결과를 출력한다.
void printPostOrder(const vector<int>& preorder, const vector<int>& inorder) {
// 트리에 포함된 노드의 수
const int N = preorder.size();
// 기저 사례: 텅 빈 트리면 곧장 종료
if (preorder.empty()) return;
// 이 트리의 루트는 전위 탐색 결과로부터 곧장 알 수 있다.
const int root = preorder[0];
// 이 트리의 왼쪽 서브트리의 크기는 중위 탐색 결과에서 루트의 위치를 찾아서 알 수 있다.
const int L = find(inorder.begin(), inorder.end(), root) - inorder.begin();
// 오른쪽 서브트리의 크기는 N에서 왼쪽 서브트리와 루트를 빼면 알 수 있다.
const int R = N - L - 1;
// 왼쪽과 오른쪽 서브트리의 순회 결과를 출력
printPostOrder(slice(preorder, 1, L+1), slice(inorder, 0, L));
printPostOrder(slice(preorder, L+1, N), slice(inorder, L+1, N));
// 후위 순위이므로 루트를 가장 마지막에 출력한다.
cout << root << ' ';
}
요새(FORTRESS)
성벽들의 정보가 주어질 때 임의의 두 지점 간을 이동하기 위해 최대 몇 번이나 성벽을 넘어야 하는지 계산하는 문제입니다. 이 문제는 언뜻 보면 트리와 별 관계가 없어 보이지만, 성벽들은 서로 닿거나 겹치지 않는다는 조건에 주목하면 성이 계층적 구조로 구성되어 있음을 알 수 있습니다. 따라서 성벽들 간의 포함 관계를 트리로 나타내서 문제를 풀어봅시다.
성벽으로 굿분된 요새 내부의 각 ‘구역’에 번호를 매깁니다. 이렇게 트리를 구성하고 나면, 한 구역에서 인접한 다른 구역으로 가기 위해 성벽을 넘는 일은 이 트리에서 간선을 따라 다른 노드로 옮겨가는 것으로 대응됩니다. 따라서 두 지점을 왕래하기 위해 성벽을 가장 많이 넘어야 하는 경우를 찾는 문제는 트리에서 가장 멀리 떨어진 두 노드를 찾는 문제가 되지요.
트리에서 최장 경로 문제를 푸는 열쇠는 최장 경로의 양 끝 노드가 항상 루트 혹은 잎 노드여야 함을 깨닫는 것입니다. 따라서 최장 경로의 길이는 다음 둘 중 더 큰 값이 됩니다.
- 가장 긴 루트-잎 경로의 길이
- 가장 긴 잎-잎 경로의 길이
이때 가장 긴 루트-잎 경로의 길이는 사실 트리의 높이기 때문에, 가장 긴 잎-잎의 경로 길이만 찾으면 됩니다. 이는 트리 순회 과정에서 각 노드마다 각 노드를 최상위 노드로 갖는 가장 긴 잎-잎 노드를 계산하고, 그중 최댓값을 선택하면 될 겁니다. 이때 경로의 올라오는 부분과 내려가는 부분의 길이는 각각의 자손 노드를 루트로 하는 서브트리의 높이에 1을 더한 것이 됩니다.
코드 21.5 트리에서 가장 긴 경로를 찾는 재귀 호출 알고리즘
struct TreeNode {
vector<TreeNode*> children;
};
// 지금까지 찾은 가장 긴 잎-잎 경로의 길이를 저장한다.
int longest;
// root를 루트로 하는 서브트리의 높이를 반환한다.
int height(TreeNode* root) {
// 각 자식을 루트로 하는 서브트리의 높이를 계산한다.
vector<int> heights;
for (int i = 0; i < root->children.size(); ++i)
heights.push_back(height(root->children[i]));
// 만약 자식이 하나도 없다면 0을 반환한다.
if (heights.empty()) return 0;
sort(heights.begin(), heights.end());
// root를 최상위 노드로 하는 경로를 고려하자.
if (heights.size() >= 2)
longest = max(longest, 2 + heights[heights.size() - 2] + heights[heights.size() - 1]);
// 트리의 높이는 서브트리 높이의 최대치에 1을 더해 계산한다.
return heights.back() + 1;
}
// 두 노드 사이의 가장 긴 경로의 길이를 계산한다.
int solve(TreeNode* root) {
longest = 0;
// 트리의 높이와 최대 잎-잎 경로 길이 중 큰 것을 계산한다.
int h = height(root);
return max(longest, h);
}