使用 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

一般在BFS中，你的节点都有一个距离场。根距离为零，那么无论何时向队列添加新节点，都将其距离设置为 n.distance+1

Answer 2

想法应该是这样的：

添加到队列的第一个节点应该有 distance = 1.
对于添加到队列的新节点：distance = actual node distance + 1
当您找到叶子时，您 return 实际节点距离。结束。

在伪代码中：

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 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));
    }
}

当然，你需要Pairclass，但我把这些细节留给你

使用 BFT 的二叉树的最小深度？

Min depth of a binary tree using BFT?

java

algorithm

binary-tree

breadth-first-search