Найти все узлы в двоичном дереве на определенном уровне (запрос интервью)

Я имею в виду на определенном уровне, а не до этого конкретного уровня. Может кто-нибудь проверить мой модифицированный алгоритм BFS? (большинство из которых взято из Википедии) 

Queue levelorder(root, levelRequested){
      int currentLevel = 0;
      q = empty queue
      q.enqueue(root)
      while not q.empty do{
           if(currentLevel==levelRequested)
                 return q;
           node := q.dequeue()
           visit(node)
           if(node.left!=null || node.right!=null){
                 currentLevel++;
                 if node.left ≠ null
                       q.enqueue(node.left)
                 if node.right ≠ null
                       q.enqueue(node.right)
           }
      }
}
2 4
algorithm binary-tree breadth-first-search

2 ответа:

Я думаю, что рекурсивное решение было бы намного более кратким: 

/*
 * node - node being visited
 * clevel - current level
 * rlevel - requested level
 * result - result queue
 */
drill (node, clevel, rlevel, result) {
  if (clevel == rlevel) {
    result.enqueue (node);
  else {
    if (node.left != null)
      drill (node.left, clevel + 1, rlevel, result);
    if (node.right != null)
      drill (node.right, clevel + 1, rlevel, result);
  }
}

Начальный вызов будет выглядеть следующим образом: drill (root, 0, n, rqueue);

22

Проблема с вашим алгоритмом заключается в том, что узлы, находящиеся на одном уровне, неправильно увеличивают количество уровней.

Пояснение:

  1. Установите уровень корня равным 0

  2. При добавлении узлов на любом уровне установите их уровень на 1 больше, чем уровень их родителя.

  3. Как только вы получите любой узел, который имеет номер уровня, равный номеру уровня, который вам требуется, просто вырвитесь из BFS и сбросьте все узлы в очереди за текущим узлом, имеющим тот же номер уровня.

Пожалуйста, смотрите комментарий для получения подробной информации.

Вот одно решение : 

void Tree::printSameLevel(int requiredLevel) {
    queue BFSQ;
    TreeNode * temp;
    BFSQ.push(getHead());
    while(!BFSQ.empty()) {
        temp = BFSQ.front();
        BFSQ.pop();
        //if the level of the current node is equal to the 
        //required level, we can stop processing now and simply 
        //remove from the queue all the elements that follow 
        //and have the same level number.
        //It follows from properties of BFS that such elements 
        //will occur in a series ( level by level traversal).
        if(temp->level == requiredLevel) {
            break;
        }
        if(temp->right) {
            BFSQ.push(temp->right);
            temp->right->level = temp->level + 1;
        }
        if(temp->left) {
            BFSQ.push(temp->left);
            temp->left->level = temp->level + 1;
        }
    }
    if(!BFSQ.empty() || requiredLevel==0) {
        cout << "Printing all the nodes at level " << requiredLevel << " : ";
        while(temp&&temp->level == requiredLevel) {
            cout << temp->data << "  ";
            temp = BFSQ.front();
            BFSQ.pop();
        }
    }
}

Вот пример вывода: 

      5    
  7       3
8   6   4   2  

TREE STATS
_____________________
Inorder Trace =  2 3 4 5 6 7 8
Height = 2
Internal Nodes = 3
Leaf Nodes = 4
Total Nodes = 7
_____________________

Trees printed above are mirrors!

Printing all the nodes at level 0 : 5  
Printing all the nodes at level 1 : 7  3

Если вам интересно, я добавил эту функцию в свою реализацию generic trees здесь. Вы найдете большое количество операций дерева Для справки (зеркало, высота, красивая печать и т. д.).

3