NeetCode #449LC-1530MediumTrees
← Back to All Problems#449 · #1530 · Number of Good Leaf Nodes Pairs(好叶子节点对的数量)
📌 Problem Statement & Constraints
Given the root of a binary tree and an integer
distance, return the number of good leaf node pairs: two leaves whose shortest path length (number of edges) is at most distance. Constraints: 1 <= number of nodes <= 2^10, 1 <= distance <= 10.💡 Core Algorithmic Approaches
- For each node, collect the distances from that node to every leaf in its subtree.
- A pair of leaves whose path passes through the node has length
d_left + d_right; count those withindistance. - Then return the collected distances incremented by 1 (for the edge to the parent), discarding any that already exceed
distance. - Pruning distances beyond
distancekeeps the lists short, which is what makes the algorithm efficient.
💻 Benchmark Python3 Implementation
class Solution:
def countPairs(self, root: Optional[TreeNode], distance: int) -> int:
self.res = 0
def dfs(node: Optional[TreeNode]) -> List[int]:
"""Distances from this node to the leaves in its subtree."""
if not node:
return []
if not node.left and not node.right:
return [0] # this node is a leaf
left = dfs(node.left)
right = dfs(node.right)
# count pairs whose path goes through this node
for l in left:
for r in right:
if l + r + 2 <= distance:
self.res += 1
# distances for the parent, pruning those already too far
return [d + 1 for d in left + right if d + 1 < distance]
dfs(root)
return self.res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * distance^2): each node's leaf-distance list has at most distance entries, and the cross-pair loop is quadratic in that.
💾 Space Complexity
O(h * distance) for the lists on the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the
+2for the two edges to the children: the distances are measured from the current node, so a pair through it costsl + r + 2. - Not pruning distances at or beyond
distance: the lists would grow unboundedly and the complexity would degrade. - Returning
[0]for a non-leaf: only leaves contribute distance 0. - Counting pairs within one subtree: the pairs must have their path pass through the current node, which is exactly the cross-product between the left and right lists.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.