java - 计算最长路径

Question

我有一个 n 叉树，其中每个节点都包含键值(整数)。我想计算树的最小深度。这是我到目前为止所想出的:

int min = 0;
private int getMinDepth(Node node, int counter, int temp){
    if(node == null){
        //if it is the first branch record min
        //otherwise compare min to this value
        //and record the minimum value
        if(counter == 0){
        temp = min;     
        }else{
        temp = Math.min(temp, min);
        min = 0;
        }
        counter++;//counter should increment by 1 when at end of branch
        return temp;
    }   
    min++;        
    getMinDepth(node.q1, counter, min);
    getMinDepth(node.q2, counter, min);
    getMinDepth(node.q3, counter, min);
    getMinDepth(node.q4, counter, min);
    return temp;
}

代码的调用方式如下:

int minDepth = getMinDepth(root, 0, 0);

这个想法是，如果树正在遍历第一个分支(分支编号由计数器跟踪)，那么我们设置临时持有者来存储该分支深度。从那时起，比较下一个分支的长度，如果它更小，则使 temp = 该长度。由于某种原因，计数器根本不增加并且始终保持为零。有人知道我做错了什么吗？

Answer 1

我认为你最好进行广度优先搜索。您当前的实现尝试是深度优先的，这意味着如果分支碰巧处于尴尬的顺序，它最终可能会探索整个树。

要进行广度优先搜索，您需要一个队列(ArrayDeque 可能是正确的选择)。然后，您需要一个包含节点和深度的小类。该算法有点像这样:

Queue<NodeWithDepth> q = new ArrayDeque<NodeWithDepth>();
q.add(new NodeWithDepth(root, 1));
while (true) {
  NodeWithDepth nwd = q.remove();
  if (hasNoChildren(nwd.node())) return nwd.depth();
  if (nwd.node().q1 != null) q.add(new NodeWithDepth(nwd.node().q1, nwd.depth() + 1));
  if (nwd.node().q2 != null) q.add(new NodeWithDepth(nwd.node().q2, nwd.depth() + 1));
  if (nwd.node().q3 != null) q.add(new NodeWithDepth(nwd.node().q3, nwd.depth() + 1));
  if (nwd.node().q4 != null) q.add(new NodeWithDepth(nwd.node().q4, nwd.depth() + 1));
}

这看起来比深度优先搜索使用更多的内存，但是当您考虑到堆栈帧消耗内存，并且这将比深度优先搜索探索更少的树时，您会发现这不是案件。可能吧。

无论如何，看看你如何处理它。