查找二叉樹的深度

我無法理解這個maxDepth代碼。任何幫助，將不勝感激。這是我遵循的片段示例。查找二叉樹的深度

int maxDepth(Node *&temp) 
{ 
    if(temp == NULL) 
    return 0; 

else 
{ 
int lchild = maxDepth(temp->left); 
int rchild = maxDepth(temp->right); 

if(lchild <= rchild) 
return rchild+1; 

else 
    return lchild+1; 

}

}

基本上，我的理解是，遞歸函數調用自身（每左右的情況下），直到它到達最後一個節點。一旦它確實返回0，那麼它就會返回0 + 1。那麼前一個節點是1 + 1。那麼下一個是2 + 1。如果有三個左邊的孩子，int lchild將返回3.並且額外的+1是根。所以我的問題是，所有這些+1從哪裏來。它在最後一個節點返回0，但爲什麼當它向左/向右的子節點上升時，它會返回0 + 1等等？我不明白爲什麼。我知道它做到了，但爲什麼？

來源

2012-10-22 Sasha

Euh，因爲如果有一個新節點，那麼深度是前一個加號，也許？ – 2012-10-22 16:32:11

請記住，在二進制樹節點最多有2名兒童（左和右）

這是一個遞歸算法，所以它調用自身結束，過度。

如果temp（正在查看的節點）爲null，則返回0，因爲此節點不存在且不應計數。這是基本情況。

如果所查看的節點不爲空，它可能有子節點。因此它獲得左子樹的最大深度（並且爲當前節點的級別加1）和右子樹（並且爲當前節點的級別加1）。然後比較兩者並返回兩者中的較大者。

它潛入兩個子樹（temp-> left和temp-> right）並重復該操作，直到它到達沒有孩子的節點。此時它將在左右兩邊調用maxDepth，它將爲null並返回0，然後開始返回調用鏈。因此，如果你有一個三節點鏈（比如說，root-left1-left2），它會下到left2並調用maxDepth（left）和maxDepth（right）。每個返回0（它們爲空）。然後它回到了左邊2。它比較，都是0，所以兩者中的較大者當然是0.它返回0 + 1。那麼我們在左邊1 - 重複，發現1是左邊的右邊（也許它們是相同的或者它沒有右邊的孩子）中較大的一個，所以它返回1 + 1。現在我們在根，同樣的事情，它返回2 + 1 = 3，這是深度。

來源

2012-10-22 16:38:02 speakingcode

都來自於這部分代碼的那些：

if(lchild <= rchild) 
    return rchild + 1; 
else 
    return lchild + 1;

您+1自己添加到樹的葉子上得到的結果。直到你退出函數的所有遞歸調用併到達根節點爲止，這些函數保持相加。

來源

2012-10-22 16:34:03 alestanis

由於深度與前一個節點計算+ 1

來源

2012-10-22 16:34:14

考慮這部分（的更大的樹）：

 A 
     \ 
     B

現在我們要計算這個treepart的深度，所以我們傳遞指針A爲PARAM。

顯然指針A不NULL，因此代碼有：

呼叫maxDepth每個A的孩子（左和右支）的。A->right是B，但A->left顯然是NULL（如A沒有左分支）
比較這些，選擇最大的價值
返回這個選擇的值+ 1（爲A本身需要的水平，沒有按」事啊）

現在我們要看看如何maxDepth(NULL)和maxDepth(B)計算。

前者是很容易的：首先檢查會讓maxDepth返回0。如果其他的孩子都太NULL，雙方的深度將等於（0），而我們必須爲A本身返回0 + 1。

但B不是空的;但它沒有分支，所以（正如我們注意到的）它的深度是1（對於NULL s，在兩個部分+ B本身，最大爲0）。我們回到A。其左分支maxDepth（NULL）爲0時，其右支的maxDepth爲1的這些最大爲1，我們必須添加1 A本身 - 所以這是2

的一點是相同的步驟A只是大樹的一部分;這個計算的結果（2）將用於更高級別的maxDepth調用。

來源

2012-10-22 16:47:02 raina77ow

深度正在使用以前的節點+ 1

來源

2012-10-22 16:54:41 acrube

要查找二叉樹最大深度繼續下去左計算Traveres樹，基本上執行DFS
或我們可以找到二進制搜索的深度樹有三種不同的遞歸方式

– using instance variables to record current depth and total depth at every level 
– without using instance variables in top-bottom approach 
– without using instance variables in bottom-up approach

來源

2013-07-13 19:15:33 user2366458

代碼段可以減少到只有：

int maxDepth(Node *root){ 
    if(root){ return 1 + max(maxDepth(root->left), maxDepth(root->right)); } 
    return 0; 
}

查看此代碼的好方法是自上而下：

如果BST沒有節點會發生什麼情況？我們將有root = NULL，該功能將立即返回預期的深度0。

現在假設該樹已經填充了多個節點。從頂部開始，對於根節點，if條件將爲true。然後我們通過將這些子樹的根傳遞到maxDepth來問，左側子樹和右側子樹的最大深度是多少。根的LST和RST都是比根更深一級，所以我們必須加一個來獲得傳遞給該函數的樹的樹的深度爲root。

來源

2015-09-09 00:10:43 Patch92

查找二叉樹的深度

回答

相關問題