Recursion

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5639 🧐 관찰 및 접근 # 이진 검색 트리의 전위 순회 결과를 이용해서 후위 순회 결과를 찾아내자! 트리가 만들어져 있다면, 후위 순회를 하는건 쉬울텐데… 전위 순회는 (루트 - 왼쪽서브트리 - 오른쪽서브트리)를 방문한다. 왼쪽 서브트리의 값은 언제나 루트보다 작고, 오른쪽 서브트리의 값은 언제나 루트보다 크므로 50 (루트) --- 30 (왼쪽 서브트리) 24 5 28 45 --- 98 (오른쪽 서브트리) 52 60 첫 입력에 대해, 이렇게 생각할 수 있지 않을까? 그리고 각 서브트리 또한 이진 검색트리이므로, 이를 재귀적으로 수행할 수 있다. 예를 들어, 왼쪽 서브트리에 대해서 30 (루트) --- 24 (왼쪽 서브트리) 5 28 --- 45 (오른쪽 서브트리) 위와 같이 말이다! 그렇다면, 재귀를 이용해서 트리를 구축하고 후위순회만 하면 끝난다. 💻 풀이 # 코드 (C++): vector<int> v; struct Node{ int val = -1; Node* left = nullptr; Node* right = nullptr; Node(int s, int e){ val = v[s]; if(s == e) return; int idx = e+1; rep(i, s+1, e+1){ if(v[i] > val){ idx = i; break; } } if(s+1 <= idx-1) left = new Node(s+1, idx-1); if(idx <= e) right = new Node(idx, e); } }; void postorder(Node* node){ if(node == nullptr) return; postorder(node->left); postorder(node->right); cout << node->val << '\n'; } void solve(){ int x; while(cin >> x) v.push_back(x); Node* root = new Node(0, v.size()-1); postorder(root); } 🔒 구현 코드 잠금