⚡Flashcard Drill➔
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

  1. For each node, collect the distances from that node to every leaf in its subtree.
  2. A pair of leaves whose path passes through the node has length d_left + d_right; count those within distance.
  3. Then return the collected distances incremented by 1 (for the edge to the parent), discarding any that already exceed distance.
  4. Pruning distances beyond distance keeps 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 +2 for the two edges to the children: the distances are measured from the current node, so a pair through it costs l + 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems