你會如何找到樹的最小深度？

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：代碼鍵入寫意，可能有語法錯誤，但我相信邏輯罰款...