題目出處
難度
easy
個人範例程式碼
# 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