Good leaf pair: 2 leaf nodes ระยะทาง shortest path <= d ใช้ DFS post-order คืน list ของ [node_ref, distance_from_this_node] สำหรับ leaf เป็น [[node, 0]] สำหรับ internal node: รวม left และ right lists เพิ่ม distance +1 ตรวจสอบทุกคู่ cross left-right ว่า distance_sum <= d
ขั้นตอนการทำงาน
- DFS function util(node) คืน list of [node, dist_from_node]
- ถ้า leaf: return [[node, 0]]
- left = util(node.left), right = util(node.right)
- เพิ่ม distance ทุก entry ใน left และ right ขึ้น 1
- นับคู่ (n in right, n1 in left) ที่ n[1] + n1[1] <= d
- return left + right
ตัวอย่างโค้ด
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 [[root, 0]]
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
# Build tree:
# 1
# / \
# 2 3
# \ / \
# 4 5 6
# / \
# 8 7
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)) # Output: 2
อินพุต/เอาต์พุต
Input: tree as above, d=4 Output: 2
Good pairs: (8,7) distance 2, (5,6) distance 2. Pairs like (7,5) distance 5 > 4 not good.
