Cho cây nhị phân và khoảng cách d. Cặp 2 nút lá khác nhau là "tốt" nếu đường đi ngắn nhất giữa chúng ≤ d. Đếm số cặp tốt.
Ví dụ: cây cho trước, d=4 → 2 cặp: (8,7) và (5,6) (khoảng cách 2), các cặp khác khoảng cách 5 > 4.
Thuật toán
- sol = 0
- DFS util(root):
- Nếu root null: return []
- Nếu root là lá: return [[0,0]] (depth=0, count=0?)
- Ngược lại: l = util(left), r = util(right)
- Tăng depth của mọi phần tử trong l và r lên 1
- Với mỗi n trong r, n1 trong l: nếu n[1]+n1[1] <= d: sol++
- Return l+r
- Gọi util(root), return sol
Code Python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def __init__(self):
self.sol = 0
def solve(self, root, d):
def util(root):
if not root:
return []
if not root.left and not root.right:
return [[0, 0]]
else:
cur = []
l = util(root.left)
r = util(root.right)
for n in l:
n[1] += 1
for n in r:
n[1] += 1
for n in r:
for n1 in l:
if n[1] + n1[1] <= d:
self.sol += 1
return l + r
util(root)
return self.sol
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(8)
root.left.right.right = TreeNode(7)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
d = 4
ob = Solution()
print(ob.solve(root, d))
Input
root = TreeNode(1)... d = 4
Output
2