思路
分別求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