看過層級遍歷後，我們來看下一個主題：樹的深度相關的主題。
平衡二元樹的特性也與樹的深度相關，在切入正題之前，我們先來題簡單的深度計算熱熱手。

Maximum Depth of Binary Tree

這題和昨天做的相反，是求樹的最大深度，同樣的，我們也可以用層級遍歷來處理他。
但相對昨天的最小深度，我們必須遍歷完整棵樹才能夠確認最大深度會是多少。
不如我們今天換個寫法，大多數的遍歷，除了迭代，就是遞迴。

寫遞迴在前中後序有稍稍提過，終止條件、遞迴函式本身的意義。
現在我們要用遞迴來寫的話，MaxDepth 的函示本身意義是，「給予一個根節點，回傳該節點的最大深度」。
我們可以先決定終止條件，也就是如果傳入的節點本身是 null，則深度是 0。
再來，什麼時候深度會增加？

• 任一節點存在的時候，也就是當訪問到的節點不為空時
• 還有當該節點有左右子樹，該節點的最大深度就有可能繼續增加
  按照這樣的邏輯去寫，其實遞迴就寫完了。

public class Solution {
    public int MaxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        return 1 + Math.Max(MaxDepth(root.left),MaxDepth(root.right));
    }
}

程式碼看起來很簡潔，但已經包含了所有 case，這就是遞迴的力量。
要想清楚終止條件、函式本身意義和關鍵參數的增減方式。
這題因為只要挖到最深就可以回傳，不用考慮往回的例子，還算是個簡單的遞迴。

Balanced Binary Tree

熱身完可以開始我們今天的正題了，也就是平衡二元樹。
在定義上，平衡二元樹指的是，任意一個節點底下的兩顆子樹，子樹深度差不超過 1(最多能差 1 層的意思)。
題目會給我們一棵樹的根節點，我們要判斷該樹是否為一顆平衡二元樹。

有了上面的深度算法，我們已經可以用同樣的方法得出任一個點的深度了。
我們再想一次 IsBalanced 這個題目給的函式，他的定義是什麼？
「給入一個根節點，回傳左子樹和右子樹是否高度差異小於 1」
而我們解題要做的就是確認每個節點的左右子樹高度差異是否小於 1，只有當整棵樹都符合條件，我們才能說他是一顆平衡二元樹。
那定義清楚了，反覆要做的事也跟題目的函式意義重疊了，我們就可以用遞迴來寫這個題目了。
終止條件一樣，如果根節點不存在，左右子樹高度皆為 0，也符合平衡二元樹的定義，所以這個 case 要回傳 true。
假設根節點存在，我們需要確認該節點的左右子樹是不是高度相差 1 以內，所以分別得出他的高度，然後相減後絕對值做確認，不符合的條件下，我們就回傳 false，因為違反了定義。
符合的條件下，為了確保整棵樹都是這樣，我們應該分別確認該節點的左右子樹是否都符合 IsBalanced 的定義，如果都符合，則這是一顆平衡二元樹。

思路說完，程式碼也就這樣寫完了。

public class Solution {
    public bool IsBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        var leftHeight = GetHeight(root.left);
        var rightHeight = GetHeight(root.right);
        if(Math.Abs(leftHeight - rightHeight) > 1){
            return false;
        }
        return IsBalanced(root.left) && IsBalanced(root.right);
    }

    public int GetHeight(TreeNode node){
        if(node == null){
            return 0;
        }
        return 1 + Math.Max(GetHeight(node.left), GetHeight(node.right));
    }
}

今天的上面這兩題，先從深度入手，然後看出深度與平衡二元樹的結合，也練習到前面題目比較少寫道的遞迴思考方式。
在結構的走訪裡，遞迴有時候反而比迴圈還要容易寫，透過不同類型的題目，熟悉各種寫法，才能在面對不同類型的題目，找出適合的解法。