一、題目介紹
今天要解的題目是LeetCode的Maximum Depth of Binary Tree，中文可以稱為「二元樹的最大深度」。

題目會給定一棵二元樹root，每個節點最多有兩個子節點，分別為left和right。需要計算從根節點（Root）到最遠葉節點（Leaf）的節點數量，也就是這棵二元樹的最大深度。

例如：

這棵樹最深的路徑為：3 → 20 → 15 或 3 → 20 → 7
總共有3個節點，因此最大深度為：3
如果root為空，也就是沒有任何節點，則最大深度為0。

二、解題思路
這題可以使用DFS（Depth-First Search，深度優先搜尋）搭配遞迴（Recursion）來解決。

DFS的概念是先深入其中一個分支，直到無法繼續往下，再回頭處理另一個分支。

對於每一個節點，可以分成兩種情況：
1. 節點為空
如果目前的節點是null或None，代表已經走到樹的最底部，因此深度為0。

2. 節點存在
如果目前節點存在，就分別計算：

• 左子樹的最大深度
• 右子樹的最大深度
  然後取兩者較大的值，再加上目前這個節點本身：最大深度 = max(左子樹深度, 右子樹深度) + 1
  因此可以透過遞迴，從葉節點一路將深度結果回傳到根節點。

三、解題流程
以以下二元樹為例：

首先從根節點3開始。
maxDepth(3)
↓
計算左子樹
↓
maxDepth(9) = 1

再計算右子樹：
maxDepth(20)
↓
左子樹：15 → 1
右子樹：7 → 1
↓
max(1, 1) + 1
↓
2

最後回到根節點：
左子樹 = 1
右子樹 = 2

max(1, 2) + 1
↓
3

因此答案為：3

這種「先往下探索，再把結果往上傳回來」的方式，就是遞迴DFS的核心概念。

四、Java實作

五、Python實作

六、時間與空間複雜度
Java

• 時間複雜度：O(n)
  • 每個節點都會被訪問一次，因此如果二元樹共有n個節點，就需要走訪n個節點。
• 空間複雜度：O(h)
  • 由於使用遞迴，每次遞迴呼叫都會存在Call Stack中。
  • 其中h代表二元樹的高度：
    • 如果樹接近平衡：O(log n)
    • 如果樹退化成單邊鏈狀：O(n)
  • 因此最壞情況下為：O(n)

Python

• 時間複雜度：O(n)
  • 每個節點只會被DFS訪問一次，因此時間複雜度為O(n)。
• 空間複雜度：O(h)
  • 遞迴過程會使用Call Stack，因此空間複雜度與樹的高度h有關，最壞情況為O(n)。

七、Java與Python解法比較

八、實作結果
Leetcode測試結果：Accepted

九、今日學習心得
今天將DFS與遞迴應用在二元樹上。

一開始看到二元樹可能會覺得節點一層一層分開，看起來比陣列或Linked List複雜，但實際上可以將問題拆成「目前節點的左子樹有多深」以及「右子樹有多深」。

透過遞迴，可以讓每個節點自己去計算左右子樹的深度，再將結果逐層回傳。

這題讓我更理解遞迴的概念：一個大問題可以拆成許多相同形式的小問題，直到遇到可以直接處理的Base Case。

同時也了解到DFS不只是單純「走訪所有節點」，還可以在走訪的過程中取得並整理資訊。這對之後學習其他Tree類型的題目會很有幫助。