題目出處
難度
easy
題目分類
Tree, Depth-First Search, Binary Tree
2026-07-29 二刷
個人範例程式碼 - 二刷 (2026/07/29)
# 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 = right
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
self.max_length = 0
def dfs(root):
if not root:
return 0
max_left = dfs(root.left)
max_right = dfs(root.right)
self.max_length = max(self.max_length, max_left + max_right)
return 1 + max(max_left, max_right)
dfs(root)
return self.max_length
算法說明
Time Complexity
O(n)
Space Complexity
O(h) # 樹高
Boundary conditions
留意 dfs 追蹤的是樹目前的最高，
而 max (left + right) 需要另外一個變數進行儲存。
2022-06-21 一刷
個人範例程式碼 - 一刷 (2022/06/21)
# 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 = right
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
return self.helper(root)[0]
def helper(self, root):
# end of recursion
if not root:
return 0, 0
# define and split
left_longest, left_diameter = self.helper(root.left)
right_longest, right_diameter = self.helper(root.right)
longest = max(left_longest, right_longest, left_diameter + right_diameter)
diameter = max(left_diameter, right_diameter) + 1
return longest, diameter
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
我們先來理解題意，這題目主要是在詢問在 Tree 中「最長可組成的邊 (diameter)」，
主要有兩種情況：
- 最長邊包含 root
- 最長邊不包含 root (最長存在子樹中)
因此我們需要同時記錄「子樹中，目前最長」與「目前最長的邊」。
- 目前最長的邊 + 1 = 向上一層的最長邊
input handling
在 dfs 內處理
Boundary conditions
在 dfs 內控制範圍，如果搜尋至 root = None，return 0, 0