지우너
[코드트리] 트리 순회법 변경2, 3 C++ 본문
전위 순회, 중위 순회가 주어졌을 때 후위 순회를 구하는 법
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> preorder;
vector<int> inorder;
vector<int> FindPostorder(int preorderStart, int preorderEnd, int inorderStart, int inorderEnd){
// 범위를 벗어나는 경우
if (preorderStart > preorderEnd || inorderStart > inorderEnd) {
return vector<int>();
}
// 1. 전위 순회의 첫 번째 노드는 루트
// 2. 중위 순회에서 루트노드를 기준으로 왼쪽 노드들은 왼쪽 서브트리
// 오른쪽 노드들은 오른쪽 서브트리
// 왼쪽 트리를 후위 순회한 결과, 오른쪽 트리를 후위 순회한 결과, 루트 노드를 재귀적으로 실행
// 1. 전위 순회의 첫 번째 노드는 루트
int root_val=preorder[preorderStart];
int root_idx =0;
for(int i=inorderStart; i<=inorderEnd; ++i){
if(inorder[i]==root_val) {
root_idx=i;
break;
}
}
// 재귀적으로 sub트리 구하기
int left_size=root_idx-inorderStart;
vector<int> leftSubtree=FindPostorder(preorderStart+1, preorderStart+left_size, inorderStart, root_idx-1 );
vector<int> rightSubtree=FindPostorder(preorderStart+left_size+1, preorderEnd, root_idx+1, inorderEnd);
// subtree 합치기
vector<int> postorder;
postorder.insert(postorder.end(), leftSubtree.begin(), leftSubtree.end());
postorder.insert(postorder.end(), rightSubtree.begin(), rightSubtree.end());
postorder.push_back(root_val);
return postorder;
}
int main() {
// input
cin >> n;
preorder.resize(n), inorder.resize(n);
for(int i=0; i<n; ++i){
cin >> preorder[i];
}
for(int i=0; i<n; ++i){
cin >> inorder[i];
}
// solution
vector<int> postorder = FindPostorder(0, n-1, 0, n-1);
// output
for(int i=0; i<n; ++i){
cout << postorder[i] << " ";
}
return 0;
}
중위 순회, 후위 순회가 주어졌을 때 전위 순회를 구하는 법
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> inorder;
vector<int> postorder;
//3
// 1 2 3 // 중위(왼 중 오)
// 1 3 2 // 후위(왼 오 중)
vector<int> FindPreorder(int inorderStart, int inorderEnd, int postorderStart, int postorderEnd){
// 종료 조건
if(inorderStart>inorderEnd || postorderStart>postorderEnd){
return vector<int>();
}
int root_val= postorder[postorderEnd];
// root가 중위 순회에서 어디에 있는지
int root_idx=0;
for(int i=inorderStart; i<=inorderEnd; ++i){
if(inorder[i]==root_val){
root_idx=i;
break;
}
}
int left_size=root_idx-inorderStart;
vector<int> leftSubtree=FindPreorder(inorderStart, root_idx-1, postorderStart, postorderStart+left_size-1);
vector<int> rightSubtree=FindPreorder(root_idx+1, inorderEnd, postorderStart+left_size, postorderEnd-1);
vector<int> preorder; // 중 왼 오
preorder.push_back(root_val);
preorder.insert(preorder.end(), leftSubtree.begin(), leftSubtree.end());
preorder.insert(preorder.end(), rightSubtree.begin(), rightSubtree.end());
return preorder;
}
int main() {
cin >> n;
inorder.resize(n), postorder.resize(n);
for(int i=0; i<n; ++i){
cin >> inorder[i];
}
for(int i=0; i<n; ++i){
cin >> postorder[i];
}
vector<int> preorder=FindPreorder(0, n-1, 0, n-1);
for(int i=0; i<n; ++i){
cout << preorder[i] << " ";
}
return 0;
}
'Problem Solving' 카테고리의 다른 글
[코드트리] 노드의 정수 계산 C++ (0) | 2024.10.07 |
---|---|
[코드트리] 트리 순회법 변경 C++ (0) | 2024.10.06 |
[코드트리] 트리 중위 순회 C++ (0) | 2024.10.02 |
[코드트리] 트리 순회 C++ (0) | 2024.10.02 |
[코드트리] 트리의 지름3 C++ (0) | 2024.10.01 |