Number of Good Leaf Nodes Pairs

Hard

Given the root of a binary tree and an integer distance, a pair of two different leaf nodes is good if the length of the shortest path between them (in edges) is less than or equal to distance. Return the number of good leaf node pairs.

Example 1

Input:  root = [1,2,3,null,4], distance = 3
Output: 1

Example 2

Input:  root = [1,2,3,4,5,6,7], distance = 3
Output: 2

Example 3

Input:  root = [7,1,4,6,null,5,3,null,null,null,null,null,null,2], distance = 3
Output: 1

Constraints

• 1 <= number of nodes <= 2^10
• 1 <= Node.val <= 100
• 1 <= distance <= 10.