인터뷰 질문에서 preorder
이진 검색 트리를 탐색하면 원래 트리를 구성하지 않고 리프 노드를 찾습니다. 나는 binary search tree
이 만족해야만하는 속성을 알고 있지만이 속성을 어떻게 활용할 수 있는지에 대한 어떤 관계도 찾을 수 없습니다. 내가 확인할 수있는 유일한 점은 preorder traversal
에있는 first node
은 항상 루트가된다는 것입니다. 또한 Google 검색은이 문제에 대한 결과를 산출하지 못했습니다. 코드를 시작하는 간단한 힌트가 충분하지 않기를 바랄뿐입니다.이진 검색 트리의 리프 노드를 찾았습니다
편집 : 나는이 솔루션을 가지고 많은 시도 후 : 매우 도움이 될 것입니다 변수 이름 이외의 개선을위한
#include<iostream>
#include<vector>
#include<string>
using namespace std;
void fl(vector<int> &v, int lo, int hi){
if (lo>hi) return;
if (lo == hi) { cout<<"leaf ^^^^^^^ "<< v[hi]<<"\n"; return; }
int root = v[lo];
int i;
for(i = lo+1 ; i <= hi ; i++) if (v[i] > root) break;
fl(v, lo+1, i -1);
fl(v, i , hi);
}
int main(){
vector<int> v1 = {8, 3, 1, 6, 4, 7, 10, 14, 13};
vector<int> v2 = {27, 14, 10, 19, 35, 31, 42};
vector<int> v3 = {9,8,7,6,5,4,3,2,1};
fl(v3,0,v3.size()-1);
return 0;
}
어떤 제안을
논리에 대한 간단한 설명은 매우 도움이 될 것입니다. 다만 그것이하는 것 – anekix