我知道如何使用堆栈和中序遍历找到树的最大深度,但我不知道如何使用堆栈或队列而不是递归调用来找到树(不一定是 BST)的最小深度.
最佳答案
这里要注意的一件事是,当您执行递归时,您正在使用您的流程执行堆栈。这通常有一些由操作系统设置的限制。因此,每次递归时,进程状态都会被推送到这个堆栈上。所以在某些时候会发生 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:代码是徒手输入的,可能有语法错误,但我相信逻辑没问题......
关于c++ - 你如何找到树的最小深度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7617919/