你会如何找到树的最小深度？

Question

我知道如何使用堆栈和inorder遍历来查找树的最大深度，但我无法弄清楚如何使用堆栈或队列而不是递归调用来找到树的最小深度（不一定是BST）。

Answer 1

这里需要注意的一点是，当您执行递归时，您正在使用流程执行堆栈。这通常有一些由OS设置的限制。所以每次递归都会将进程状态压入这个堆栈。所以在某些时候会发生stackoverflow。

如果你最终做了一个递归迭代版本，注意这里的区别在于这个栈实现是由你维护的。有很多涉及到更多的工作，但计算器是避免...

我们可以做一些类似以下（递归版本） -

MIN-VALUE

int min = INT_MAX; 
void getMin(struct node* node) 
{ 
    if (node == NULL) 
      return; 

    if(node->data < min) 
      min = node->data; 

    getMin(node->left); 
    getMin(node->right); 

    return min; 
} 

另外，您可以使用min-heap这可以在一段时间内为您提供最小的价值

UPDATE：既然你改变了你的问题，以最小深度

MIN-深度

#define min(a, b) (a) < (b) ? (a) : (b) 

typedef struct Node 
{ 
    int data; 
    struct Node *left, *right; 

}Node; 

typedef Node * Tree; 

int mindepth(Tree t) 
{ 
    if(t == NULL || t->left == NULL || t->right == NULL) 
     return 0; 

    return min(1 + mindepth(t->left), 1 + mindepth(t->right)); 
} 

PS：代码键入写意，可能有语法错误，但我相信逻辑罚款...