543. 二叉樹的直徑

一、算法邏輯（逐步通順講解每一步思路）

🎯 問題目標：

求二叉樹中任意兩個節點之間的最長路徑（以邊數計算）。

---

? 1?? 初始化變量

• ans 用于記錄目前遍歷過程中的最大直徑（最長路徑上的邊數）；

• 與上一版本不同：本實現中，返回的深度以“邊數”定義，而不是“節點數”；

  • 即：空節點深度為 -1，葉子節點深度為 0。

---

? 2?? 定義遞歸函數 depth(node)

目標：返回當前 node 為根節點的最大深度（邊數表示）。

處理流程如下：

? 遞歸基：

• 如果 node 是 None，說明是空節點，返回 -1。

? 正常遞歸：

• 遞歸獲取左右子樹的深度，并在返回值上 +1，表示當前節點比子樹多一層邊：

? 直徑更新：

• 每個節點可能作為一條最長路徑的“中心節點”，該路徑長度為 L + R（左右邊之和）；

• 用這個值更新最大值 ans。

? 返回當前節點的最大深度（左右中更大的那一個）：

---

? 3?? 主調用邏輯

• 從根節點開始深度遍歷；

• 遞歸完成后，ans 中即保存了整棵樹的最大直徑（邊數形式，無需再減 1）；

• 最終返回 ans。

二、核心點總結

這段實現與傳統寫法不同之處在于：

? 把“深度”定義為邊數而不是節點數，從而避免最后再手動減 1 的步驟，計算更直接。

• 使用 nonlocal ans 來更新封閉作用域內的變量；

• 所有的直徑判斷都在遞歸過程中逐層進行更新；

• 核心仍是：后序遍歷，自底向上構建子樹信息并合并更新全局答案。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = rightclass Solution:def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:ans = 0def depth(node: Optional[TreeNode]) -> int:if node is None:return -1L = depth(node.left)+1R = depth(node.right)+1nonlocal ansans = max(ans, L+R)return max(L, R)depth(root)return ans

三、時間復雜度分析

• 每個節點只訪問一次；

• 每次訪問只做常數次操作；

時間復雜度：O(n)，其中 n 為節點數。

---

四、空間復雜度分析

• 空間主要來自遞歸調用棧；

• 最壞情況為鏈狀樹 → O(n)，最好情況為平衡樹 → O(log n)；

空間復雜度：O(h)，其中 h 是樹的高度。

---

? 總結一句話

本算法通過“將深度定義為邊數”的方式，避免了最終再減 1 的步驟，依然使用后序遞歸 + 非局部變量更新最大直徑的策略，在 O(n) 時間、O(h) 空間內求出二叉樹的最大直徑。該寫法更貼近“邊”的定義，簡潔且邏輯緊湊。