주어진 범위 내에서 BST의 숫자를 포함하는 단일 연결 목록 만들기

Question

주어진 범위 내에서 BST에있는 모든 정수를 찾는 데 관심이 있습니다. BST 노드를 사용하여 만든 경우 따라서 단일 링크 된 목록을 사용해야 할 거라고 어떻게 내가 갈 것이라고 궁금하네요. 반환되는 연결된 목록의 항목 순서는 중요하지 않습니다.

예를 들어

의 범위는 [6, 13]는 다음 목록을 포함한다 트리 아래와 같이 고려 6-> 7-> 8> 10> 13 13 → 10-> 8-> 7-> 6. 앞에서 말했듯이 반환 된 목록에는 순서가 중요하지 않습니다.

또한 런타임 제한 조건은 O (n)입니다. 여기서 n은 트리의 노드 수입니다.

미리 감사드립니다.

Answer 1

당신은 단지

가의 2 스택 시작하자 2 스택을 ... 사용하여이 작업을 수행 할 수있다, (1) (예를 들어, 당신이 방문해야 노드를 포함) 간단한 할 일 스택이고, 다른 하나는 결과와 중첩된다.

루트 노드로 시작하고 노드가 범위 내에 있으면 결과 스택에 밀어 넣고 두 자식을 모두 실행 스택으로 밀어 넣습니다. 만약 범위를 벗어나면 2 가지 경우가 발생할 수 있습니다 : 1.) 범위 내에서 가장 작은 값보다 작습니다. - 바로 가기 스택에 오른쪽 자식을 넣으십시오. 2) 우리 범위에서 가장 큰 값보다 큽니다 -> 잭 스택에

좋아요 그래서 몇 가지 유용한 알고리즘이 점을 만들 수 있습니다 :이 언어와 같은 C 단지 의사 코드 ++이라고

List<BSTNode*> FindAllInRange(BSTNode* root, int low, int high) 
{ 
    Stack<BSTNode*> todo;    //< Todo stack 
    Stack<BSTNode*> results;   //< Results stack 

    // Start with root node 
    todo.push(root); 

    // While we have nodes to process 
    while(todo.size() > 0) 
    { 
     // Get top node, and pop it from stack 
     BSTNode* curr = todo.top(); 
     todo.pop(); 

     // If its value is less than the lowest value in range 
     if(curr->value < low) 
     { 
      // Push right children if exists (as it may be higher than lowest value in range) 
      if(node->right) 
       todo.push(node->right); 
     } 
     // If its value is greater than the highest value in range 
     else if(curr->value > high) 
     { 
      // Push left children if exists (as it may be lower than highest value in range) 
      if(node->left) 
       todo.push(node->left); 
     } 
     // Otherwise (we're in range) 
     else 
     { 
      // Push current node to results stack 
      results.push(curr); 

      // If right node exists, push it on todo stack 
      if(node->right) 
       todo.push(node->right); 

      // If left node exists, push it on todo stack 
      if(node->left) 
       todo.push(node->left); 
     } 
    } 

    // Now you just have to convert the stack to list (and possibly sort it, reverse sort it, ...) 
    return results.ConvertToList(); 
} 

참고.

Answer 2

저는 BST에 대한 기본 지식이 있습니다. 트리에서 정렬 된 요소 집합을 검색하는 것이 실제로 매우 쉽다는 것을 잘 알고 있어야합니다. LVR/RVL 트래버스에 익숙하다면 "답변"으로 건너 뛸 수 있습니다.

대개 세 글자 LVR의 조합으로 설명되어있는 트리를 순회 :

는 순환 적 트리를 통과. L가 남습니다. R이 맞습니다. V은 방문을 의미합니다.

트리를 탐색 할 때 따라하는 패턴을 설명합니다. L은 트리가 존재할 경우 왼쪽 노드로 내려가는 것을 의미합니다. 오른쪽에는 R입니다. V은 인쇄와 같이 현재 노드에서 일부 작업을 의미합니다. 그것은 재발을 사용합니다!. 그것은 아주 중요합니다.

지금. 정렬 된 집합을 얻는 방법. LVR 방문은 인쇄 또는 밀기를 의미 할 때 간단합니다.

예 -을 통해 완전한 산책 :

(8) You start in root. `L` - go left. 
    (3) You are in (3). You go `LVR` for this node again - recurrence. `L` 
    (1) You are in (1). Now *again* `LVR`. 
    However there is no left node so we go to `V` - visit/print 1. Now `R` - no right node. End. By recurrence we go back to 3. 
    (3) - We're done with `L`. We do `V`. Print 3. 
    (3) - `R`. 
    (6) You are in (6) - `LVR` again. 'L' 
     (4) You are in (4) - `L` does not exists. Print 4. `R` does not exist. Back one level. 
    (6) - `V`. Print 6. 
    (6) - `R`. 
     You are in (7) - `L` does not exists. Print 7. `R` does not exist. Back one level. 
    (6) - `LVR` Done. Back one level. 
    (3) - `LVR` Done. Back one level. 
(8) - `R`. 
    (10) You are in 10. `L` Does not exist. 
    (10) `V`. Print 10. 
    (10) `R`. 
    (14) You are in 14. 
    (14) `L`. 
     (13) You are in 13. `L` does not exists. Print 14. `R` does not exist. Back one level. 
    (14) `V`. Print 14. 
    (14) `R`. Does not exist. Back one level. 
    (10) Done with `R`. Back one level. 
(8) Done with `R`. Back one level. 
Haha we were on root node so we are done. 

당신이 인쇄를 수행됩니다. 그것은 당신을 가장 낮은 것에서 가장 높은 것 순으로 전체 세트를 인쇄하게 할 것입니다.RVL 패턴은 비슷하지만 첫 번째로 이동하기 때문에 대부분의 노드를 먼저 방문하므로 순서가 내림차순이됩니다. 마법이 없으므로 각 노드를 정확히 한 번 방문하면 시간 복잡도는 O(n)이됩니다.

답 :

쉬운 방법입니다. 보통 LVR을 트래버스합니다. 그러나 범위에 맞는 경우에만 숫자를 인쇄하십시오. 조금 더 힘들지 만 평균 및 극단적 인 경우가 더 좋습니다. 시작 노드를 찾습니다. 그런 다음 탐색을 시작하고 각 방문에서 상위 데이터를 비교하고 노드 데이터가이를 초과하면 중지합니다.

물론 인쇄 대신 스택이나 목록 (예 : 목록)을 사용하여 요소를 정렬 된 순서로 저장하려고 할 수 있습니다.