直觀的方式來了解樹遞歸 - 編寫代碼，以檢查是否二叉樹是平衡

Question

問：

實現一個功能，以檢查是否二叉樹是平衡的（即沒有0​​兩個節點的高度不同從根本上超過1）。

解決方案：

int maxDepth(Node *root) 
{ 
    if(!root) return 0; 

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

    return 1 + min(minDepth(root->left), minDepth(root->right)); 
} 
bool isBalanced(Node *root) 
{ 
    return maxDepth(root)-minDepth(root) <= 1; 
} 

有人可以幫助我瞭解這個解決方案背後的直覺？我努力「看到」樹算法背後的遞歸。我知道maxDepth和minDepth應該分別找到樹中最大深度和最小深度節點的高度，但我不明白遞歸如何工作。

更重要的是，我不太清楚我可以自己想出這個解決方案。因此，有關如何處理一般樹問題的任何提示將不勝感激。

Answer 1

理解的最好方法是看一下例子：

a 
/\ 
b c 
    /\ 
    d e 

，當你調用根節點「A」會出現什麼下面的代碼做maxDepth？

return 1 + max(maxDepth(root->left), maxDepth(root->right)); 

它將返回1 + 的maxDepth('b')或maxDepth('c')最大

maxDepth('b')將返回1因爲：

1 + max(maxDepth(NULL), maxDepth(NULL)) = 1 + (max (0,0)) = 1 + 0 = 0; 

以上從'B' 得到NULL秒 - >左和'b' - >右邊

左右，又回到了MAXDEPTH（ 'A'）現在我們知道，它返回：

maxDepth('a') = 1 + max(1, maxDepth('c')); 

maxDepth('c')將遵循相同的步驟，並返回2。因此：

maxDepth('a') = 1 + max(1, 2) = 1 + 2 = 3 

爲minDepth（）該流程與使用分鐘（）而不是max（）的唯一區別是相同的。