计算最长路径

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

这看起来像它使用比深度优先搜索更多的内存，但是当你考虑到堆栈帧消耗内存，并认为这将探索少树比深度优先搜索，你会发现情况并非如此。大概。

无论如何，看看你如何继续。

Answer 2

您正在通过值传递计数器变量，而不是通过引用。因此，对其进行的任何更改都是当前堆栈帧的局部变化，并且只要函数返回并且该帧被弹出堆栈，就会丢失。 Java不支持通过引用传递原语（或者其他任何东西），所以你必须将它作为单个元素数组传递或者将其包装在一个对象中以获得所需的行为。

这里有一个简单的（未经测试）版本，避免需要通过引用传递一个变量：以上

private int getMinDepth(QuadTreeNode node){ 
    if(node == null) 
     return 0; 
    return 1 + Math.min(
      Math.min(getMinDepth(node.q1), getMinDepth(node.q2)), 
      Math.min(getMinDepth(node.q3), getMinDepth(node.q4))); 
} 

无论你的版本和一个是低效的，因为他们搜索整个树，当你真的只需要搜索到最浅的深度。为了有效地执行此操作，请使用队列来执行像汤姆建议的广度优先搜索。但请注意，获得这种额外速度所需的权衡是队列使用的额外内存。

编辑：

我决定继续写，不假设你有一个类，跟踪了节点的深度（如汤姆的NodeWithDepth）广度优先搜索版本。再一次，我没有测试过它，甚至没有编译过它......但是我认为即使它不能立即开始工作，它应该足以让你继续。此版本应该在大型复杂树上执行得更快，但也会使用更多内存来存储队列。

private int getMinDepth(QuadTreeNode node){ 
    // Handle the empty tree case 
    if(node == null) 
     return 0; 

    // Perform a breadth first search for the shallowest null child 
    // while keeping track of how deep into the tree we are. 
    LinkedList<QuadTreeNode> queue = new LinkedList<QuadTreeNode>(); 
    queue.addLast(node); 
    int currentCountTilNextDepth = 1; 
    int nextCountTilNextDepth = 0; 
    int depth = 1; 
    while(!queue.isEmpty()){ 
     // Check if we're transitioning to the next depth 
     if(currentCountTilNextDepth <= 0){ 
      currentCountTilNextDepth = nextCountTilNextDepth; 
      nextCountTilNextDepth = 0; 
      depth++; 
     } 
     // If this node has a null child, we're done 
     QuadTreeNode node = queue.removeFirst(); 
     if(node.q1 == null || node.q2 == null || node.q3 == null || node.q4 == null) 
      break; 
     // If it didn't have a null child, add all the children to the queue 
     queue.addLast(node.q1); 
     queue.addLast(node.q2); 
     queue.addLast(node.q3); 
     queue.addLast(node.q4); 
     // Housekeeping to keep track of when we need to increment our depth 
     nextCountTilNextDepth += 4; 
     currentCountTilNextDepth--; 
    } 

    // Return the depth of the shallowest node that had a null child 
    return depth; 
} 

Answer 3

计数器总是停留在零，因为java中的原语是按值调用的。这意味着，如果您覆盖函数调用中的值，调用者将看不到更改。或者如果您熟悉C++符号，那么它是foo（int x）而不是foo（int & x）。

一个解决方案是使用Integer对象，因为对象是通过引用来调用的。

由于您对最小深度感兴趣，广度优先解决方案可以正常工作，但您可能会遇到大型树木的内存问题。

如果您认为树可能变得相当大，IDS解决方案将是最好的。通过这种方式，您将获得广度优先变体的时间复杂度以及深度优先解决方案的空间复杂性。

这是一个小例子，因为IDS并不像它的弟兄那样广为人知（尽管对于严肃的东西更有用！）。为了简单起见，我假设每个节点都有一个带有子节点的列表（因为它更通用）。

public static<T> int getMinDepth(Node<T> root) { 
    int depth = 0; 
    while (!getMinDepth(root, depth)) depth++; 
    return depth; 
} 

private static<T> boolean getMinDepth(Node<T> node, int depth) { 
    if (depth == 0) 
     return node.children.isEmpty(); 
    for (Node<T> child : node.children) 
     if (getMinDepth(child, depth - 1)) return true; 
    return false; 
} 

对于一个简短的说明见http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search