백준 2263번 문제(트리의 순회) C++ 풀이 [로밍맨]

문제 링크

https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

 

정답 코드는 아래와 같습니다.

#include <iostream>
 
class Node {
public:
  Node(int value, Node* left, Node* right)
      : value_(value), left_(left), right_(right) {
  }
 
  ~Node() {
    delete left_;
    delete right_;
  }
 
  int value_;
  Node* left_;
  Node* right_;
};
 
int findIdx(int* arr, int idx, int item) {
  while (true) {
    if (arr[idx] == item) {
      return idx;
    }
    ++idx;
  }
}
 
Node* calc(int* inorder, int* postorder, int iStart, int pStart, int sz) {
  if (sz <= 0) {
    return nullptr;
  }
  int root = postorder[pStart + sz - 1];
  int rIdx = findIdx(inorder, iStart, root);
  int leftSize = rIdx - iStart;
  int rightSize = sz - leftSize - 1;
  Node* left = calc(inorder, postorder, iStart, pStart, leftSize);
  Node* right = calc(inorder, postorder, rIdx + 1, pStart + leftSize, rightSize);
  return new Node(root, left, right);
}
 
void prePrint(Node* tree) {
  if (nullptr == tree) {
    return;
  }
  std::cout << tree->value_ << " ";
  prePrint(tree->left_);
  prePrint(tree->right_);
}
 
int main(int argc, char* argv[]) {
  int n = 0;
  std::cin >> n;
  int* inorder = new int[n]();
  int* postorder = new int[n]();
  for (int i=0; i<n; ++i) {
    std::cin >> inorder[i];
  }
  for (int i=0; i<n; ++i) {
    std::cin >> postorder[i];
  }
  Node* tree = calc(inorder, postorder, 0, 0, n);
  prePrint(tree);
  std::cout << std::endl;
  delete tree;
  delete[] inorder;
  delete[] postorder;
  return 0;
}

 

728x90

 

파이썬 버전 풀이 소스코드는 아래 링크 참고 바랍니다.

https://roamingman.tistory.com/18

백준 2263번 문제(트리의 순회) 파이썬(Python) 풀이 [로밍맨]

 

다른 언어로 풀이하지 않을 생각입니다만, 본 문제의 C++ 정답 코드가 필요한 상황이 발생하여, C++ 코드 작성한 김에 소스코드 공유합니다.

어떤 컨셉으로 어떤 방식으로 풀었는지는 아래 영상(파이썬)과 상기 파이썬 버전 포스팅을 참고해주세요.

https://www.youtube.com/watch?v=18ncLrRKGiM 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)