Минимальная глубина бинарного дерева с использованием BFT?

Question

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

public int BFS(Node root){ 
    if (root == null) return 0; 
    Queue<Node> q = new LinkedList<Node>(); 
    int min = 1; 
    q.clear(); // I saw this in a queue example, unsure if needed 
    q.add(root); 
    while (! q.isEmpty()){ 
     Node n = q.remove(); 
     if (n.left != null) q.add(n.left); 
     if (n.right != null) q.add(n.right); 
    } 
} 

Я не уверен, где обновить счетчик минимальной высоты. Я думал о том, чтобы поместить его внутри операторов if в переменные цикла temp l & r, где я бы установил их в 1, если левый или правый не равен null, 0 else. Затем добавьте мин этих 2 к минимальной высоте, но это работает только, если я на одном уровне выше листьев.

Answer 1

Идея должна быть что-то вроде:

• Первого узла добавляется в очередь должен иметь distance = 1.
• Для новых узлов, добавленных в очередь: distance = actual node distance + 1
• Когда вы найдете лист, вы возвращаете фактическое расстояние между узлами. КОНЕЦ.

В псевдокоде:

root.depth := 1 
q := create queue 
q.add(root) 

while q is not empty 
    Node n := q.dequeue() 

    if (n is leaf) then 
     return n.depth 

    if (n.left is not null) then 
     n.left.depth := n.depth + 1 
     q.add(n.left) 
    if (n.right is not null) then 
     n.right.depth := n.depth + 1 
     q.add(n.right) 

return 0 

Answer 2

Как правило, в BFS ваши узлы имеют поле расстояния. расстояние корней равно нуль, то при добавлении нового узла в очередь, вы установите ее расстояние до n.distance +-

Answer 3

Вы можете использовать очередь пар (узел, глубина). Поскольку поиск BFT, первый лист содержит минимальную глубину.

на основе коды, алгоритм будет что-то вроде этого (псевдо кода Java):

public int BFS(Node root) 
{ 
    if (root == null) 
    return 0; 

    Queue<Pair<Node,int>> q = new LinkedList<Pair<Node,int>>(); 
    q.add(new Pair(root, 0)); 

    while (! q.isEmpty()) { 

     Pair p = q.remove(); 
     Node n = p.getFirst(); 

     if (n.left == null && n.right == null) // is this a leaf? 
      return p.getSecond(); // yes! ==> p.getSecond() is its min depth 

     if (n.left != null) 
      q.add(new Pair(n.left, p.getSecond() + 1)); 
     if (n.right != null) 
      q.add(new Pair(n.right, p.getSecond() + 1)); 
    } 
} 

Конечно, вам нужна Pair класса, но я оставляю вам эти детали