Re: [閒聊] 每日leetcode已回收
思路
分別求left subtree的leaves與現在root的距離
right subtree也求
然後兩邊相加看有多少個pair符合條件
最後就把這兩個距離list concate在一起往上送
這樣就也不會重複算到pair
真佩服自己沒看安沙想到這個
第一眼覺得這個很難==
def countPairs(self, root: TreeNode, distance: int) -> int:
ans = 0
def dfs(root) -> List:
nonlocal ans
if not root:
return []
if not root.right and not root.left:
return [1]
left_d = dfs(root.left)
right_d = dfs(root.right)
for d_l in left_d:
for d_r in right_d:
if d_l + d_r <= distance:
ans += 1
return [d+1 for d in left_d] + [d+1 for d in right_d]
dfs(root)
return ans
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721316105.A.45D.html
※ 編輯: DJYOMIYAHINA (125.229.37.69 臺灣), 07/18/2024 23:22:11
推
07/18 23:25,
1年前
, 1F
07/18 23:25, 1F
討論串 (同標題文章)
完整討論串 (本文為第 520 之 1553 篇)：