題目描述：

給定一個二叉樹，找出其最大深度。

二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

說明： 葉子節點是指沒有子節點的節點。

示例：

給定二叉樹 ［3，9，20，null，null，15，7］，

返回它的最大深度 3 。

樹的定義

首先，給出我們將要使用的樹的結點 TreeNode 的定義。

方法一、遞迴：

演算法

直觀的方法是透過遞迴來解決問題。在這裡，我們演示了 DFS（深度優先搜尋）策略的示例。

複雜度分析

時間複雜度：我們每個結點只訪問一次，因此時間複雜度為 O（N）， 其中 N

是結點的數量。

空間複雜度：在最糟糕的情況下，樹是完全不平衡的，

例如

每個結點只剩下左子結點，遞迴將會被呼叫 N

次（樹的高度），因此保持呼叫棧的儲存將是 O（N）。但在最好的情況下（樹是完全平衡的），樹的高度將是 log⁡（N）。因此，在這種情況下的空間複雜度將是 O（log⁡（N））。

方法二、迭代：

我們還可以在棧的幫助下將上面的遞迴轉換為迭代。

我們的想法是使用 DFS 策略訪問每個結點，同時在每次訪問時更新最大深度。

所以我們從包含根結點且相應深度為 1 的棧開始。然後我們繼續迭代：將當前結點彈出棧並推入子

結點

。每一步都會更新深度。

複雜度分析

時間複雜度：O（N）。

空間複雜度：O（N）。