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