c++ - 你如何找到树的最小深度？

Question

我知道如何使用堆栈和中序遍历找到树的最大深度，但我不知道如何使用堆栈或队列而不是递归调用来找到树(不一定是 BST)的最小深度.

Answer 1

这里要注意的一件事是，当您执行递归时，您正在使用您的流程执行堆栈。这通常有一些由操作系统设置的限制。因此，每次递归时，进程状态都会被推送到这个堆栈上。所以在某些时候会发生 stackoverflow。

如果你最终做的是迭代版本而不是递归版本，请注意这里的区别是这个堆栈实现是由你维护的。涉及更多工作，但避免了 stackoverflow...

我们可以做类似下面的事情(递归版本)-

最小值

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这会在恒定时间内为您提供最小值。

更新:由于您将问题更改为最小深度

最小深度

#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:代码是徒手输入的，可能有语法错误，但我相信逻辑没问题......