2017-02-16 5 views
0

인터뷰 질문에서 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; 
} 

어떤 제안을

답변

0

의 전순에서 리프 노드를 인쇄해야이 프로그램 BST. 이 프로그램은 꽤 자명하다.

public static void findLeafs(int[] arr) { 
     if (arr == null || arr.length == 0) 
      return; 

     Stack<Integer> stack = new Stack<>(); 
     for(int n = 1, c = 0; n < arr.length; n++, c++) { 
      if (arr[c] > arr[n]) { 
       stack.push(arr[c]); 
      } else { 
       boolean found = false; 
       while(!stack.isEmpty()) { 

        if (arr[n] > stack.peek()) { 
         stack.pop(); 
         found = true; 
        } else 
         break;  
       } 
       if (found) 
        System.out.println(arr[c]); 
      } 

     } 
     System.out.println(arr[arr.length-1]); 
    } 
+0

논리에 대한 간단한 설명은 매우 도움이 될 것입니다. 다만 그것이하는 것 – anekix

0
def getLeafNodes(data): 
    if data: 
     root=data[0] 
     leafNodes=[] 
     process(data[1:],root,leafNodes) 
     return leafNodes 

def process(data,root,leafNodes): 
    if data: 
     left=[] 
     right=[] 
     for i in range(len(data)): 
      if data[i]<root: 
       left.append(data[i]) 
      if data[i]>root: 
       right.append(data[i]) 

     if len(left)==0 and len(right)==0: 
      leafNodes.append(root) 
      return 
     if len(left)>0: 
      process(left[1:],left[0],leafNodes) 
     if len(right)>0: 
      process(right[1:],right[0],leafNodes) 
    else: 
     leafNodes.append(root) 

#--Run-- 
print getLeafNodes([890,325,290,530,965]) 
관련 문제