java - 使用 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);
    }
 }

我不确定在哪里更新最小高度计数器。我曾考虑过将它作为临时循环变量 l 和 r 放在 if 语句中，如果左边或右边不为空，我将它们设置为 1，否则为 0。然后将这 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