---

1530. 好叶子节点对的数量

• 标签：树、深度优先搜索、二叉树
• 难度：中等

题目链接

• 1530. 好叶子节点对的数量 - 力扣

题目大意

描述：给定一棵二叉树的根节点 $root$ 和一个整数 $distance$。如果两个叶子节点之间的最短路径长度 $\le distance$，则称它们为一对"好叶子节点对"。

要求：返回好叶子节点对的数量。

说明：

• 节点数 $[1, 2^{10}]$。
• $1 \le distance \le 10$。

示例：

• 示例 1：

输入：root = [1,2,3,null,4], distance = 3
输出：1
解释：树的叶节点是 3 和 4 ，它们之间的最短路径的长度是 3 。这是唯一的好叶子节点对。

• 示例 2：

输入：root = [1,2,3,4,5,6,7], distance = 3
输出：2
解释：好叶子节点对为 [4,5] 和 [6,7] ，最短路径长度都是 2 。但是叶子节点对 [4,6] 不满足要求，因为它们之间的最短路径长度为 4 。

解题思路

思路 1：DFS + 距离计数

1. 核心思想

对于每个节点，递归计算其子树中所有叶子节点到该节点的距离列表。然后合并左右子树的叶子距离列表，统计跨左右子树的叶子对。

具体地，后序遍历：

• 如果当前节点是叶子节点，返回 $[1]$（叶子到父节点的距离为 $1$）。
• 否则，递归得到左子树叶子距离列表 $left\_list$ 和右子树 $right\_list$。
• 统计跨左右子树的叶子对：对于每个 $l \in left\_list$，每个 $r \in right\_list$，如果 $l + r \le distance$，计数加 $1$。
• 返回合并后的距离列表（每个距离加 $1$ 表示到当前节点的父节点的距离），只保留 $\le distance$ 的。

2. 具体步骤

第 1 步：$ans = 0$。

第 2 步：递归 $dfs(node)$：

• 如果 $node$ 为空，返回 $[]$。
• 如果 $node$ 为叶子（左右孩子均为空），返回 $[1]$。
• 否则：$left = dfs(node.left)$，$right = dfs(node.right)$。
• 对 $l \in left$，$r \in right$：如果 $l + r \le distance$，$ans += 1$。
• 将 $left$ 和 $right$ 合并，每个元素加 $1$，过滤掉 $> distance$ 的，返回。

第 3 步：返回 $ans$。

3. 复杂度分析

每个节点返回的列表长度不超过 $distance$（因为只保留 $\le distance$ 的）。所以合并操作 $O(distance^2)$。

总时间复杂度 $O(n \times distance^2)$。由于 $distance \le 10$，可视为 $O(n)$。

4. 举例说明

以 $root = [1,2,3,null,4], distance = 3$ 为例：

    1
   / \
  2   3
   \
    4

叶子节点：$4$ 和 $3$。

• $dfs(4)$：叶子，返回 $[1]$。
• $dfs(2)$：
  • $left = dfs(null) = []$
  • $right = dfs(4) = [1]$
  • 无跨左右比较
  • 合并后加 $1$ → $[2]$
• $dfs(3)$：叶子，返回 $[1]$。
• $dfs(1)$：
  • $left = dfs(2) = [2]$（叶子 $4$ 到 $1$ 的距离）
  • $right = dfs(3) = [1]$（叶子 $3$ 到 $1$ 的距离）
  • 跨左右：$2 + 1 = 3 \le 3$，$ans = 1$。
  • 合并后加 $1$ → $[3,2]$。

返回 $1$。

思路 1：代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countPairs(self, root: TreeNode, distance: int) -> int:
        ans = 0

        def dfs(node):
            nonlocal ans
            if not node:
                return []
            if not node.left and not node.right:
                return [1]  # 叶子节点到父节点的距离

            left = dfs(node.left)
            right = dfs(node.right)

            # 统计跨左右子树的叶子对
            for l in left:
                for r in right:
                    if l + r <= distance:
                        ans += 1

            # 合并左右列表，加 1 后返回
            res = []
            for d in left + right:
                if d + 1 <= distance:
                    res.append(d + 1)
            return res

        dfs(root)
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n \times distance^2)$，$distance \le 10$，近似 $O(n)$。
• 空间复杂度：$O(n \times distance)$，每个节点返回 $\le distance$ 的列表。