LeetCode 题解工作台
好叶子节点对的数量
给你二叉树的根节点 root 和一个整数 distance 。 如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对 。 返回树中 好叶子节点对的数量 。 示例 1： 输入： root = [1,2,3,null,4], distanc…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
题目求一个二叉树好叶子节点的对数，答案可以拆分为三部分之和：左子树好叶子节点的对数、右子树好叶子节点的对数，以及左子树叶子节点与右子树叶子节点组成的好叶子节点的对数。 递归求解即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你二叉树的根节点 root 和一个整数 distance 。
如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对 。
返回树中 好叶子节点对的数量 。
示例 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 。
示例 3：
输入：root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3 输出：1 解释：唯一的好叶子节点对是 [2,5] 。
示例 4：
输入：root = [100], distance = 1 输出：0
示例 5：
输入：root = [1,1,1], distance = 2 输出：1
提示：
tree的节点数在[1, 2^10]范围内。- 每个节点的值都在
[1, 100]之间。 1 <= distance <= 10
解题思路
方法一：递归
题目求一个二叉树好叶子节点的对数，答案可以拆分为三部分之和：左子树好叶子节点的对数、右子树好叶子节点的对数，以及左子树叶子节点与右子树叶子节点组成的好叶子节点的对数。
递归求解即可。
时间复杂度 ，其中 是二叉树的节点数，而 和 分别是二叉树的高度和距离限制。空间复杂度 ，为递归栈空间。
# 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:
def dfs(root, cnt, i):
if root is None or i >= distance:
return
if root.left is None and root.right is None:
cnt[i] += 1
return
dfs(root.left, cnt, i + 1)
dfs(root.right, cnt, i + 1)
if root is None:
return 0
ans = self.countPairs(root.left, distance) + self.countPairs(
root.right, distance
)
cnt1 = Counter()
cnt2 = Counter()
dfs(root.left, cnt1, 1)
dfs(root.right, cnt2, 1)
for k1, v1 in cnt1.items():
for k2, v2 in cnt2.items():
if k1 + k2 <= distance:
ans += v1 * v2
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N \cdot D) |
| 空间 | O(H) |
面试官常问的追问
外企场景- question_mark
Ensure the candidate demonstrates an understanding of DFS traversal and pruning techniques.
- question_mark
Look for clarity in identifying leaf nodes and how they pair within the given distance.
- question_mark
Assess how efficiently the candidate handles the tree structure and memory usage during traversal.
常见陷阱
外企场景- error
Incorrectly identifying leaf nodes, especially in non-binary trees.
- error
Failing to prune the DFS search when the distance exceeds the threshold, leading to unnecessary computations.
- error
Not handling the edge cases where the tree has only one node or no valid pairs.
进阶变体
外企场景- arrow_right_alt
Modifying the distance threshold dynamically during DFS traversal.
- arrow_right_alt
Handling trees with more complex structures such as unbalanced binary trees.
- arrow_right_alt
Counting pairs with different criteria, such as considering paths longer than the given distance.