1530. 好叶子节点对的数量
前言
「力扣题解」系列致力于分享有价值的题目、探讨更优秀的解法。
这是本系列的第 13 篇题解，更多题解关注 Somnia1337@力扣。
题目描述
难度：🟡中等
给你二叉树的根节点 root 和一个整数 distance。
如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance，那它们就可以构成一组 好叶子节点对。
返回树中好叶子节点对的数量。
输入: root=[1,2,3,4,5,6,7], distance=3
输出: 2
解释: 好叶子节点对为 [4,5] 和 [6,7], 最短路径长度都是 2; 但是叶子节点对 [4,6] 不满足要求, 因为它们之间的最短路径长度为 4解题思路
对树后序遍历，获取每个结点 node 的左右子树中叶结点的深度计数。
以上图为例，假设当前结点为 1，其左子结点为 2，左子树中有 2 个深度为 2 的叶结点，没有其他深度的叶结点，用数组表示就是 L = [0,0,2,0]，其中 L[i] 表示左子树中深度为 i 的叶结点数量；右子树同理。
获取了左右子树的数组 L、R 后，组合其中的距离之和 <= distance 的叶结点数量。
在结点 1 处，L = R = [0,0,2,0]，结点的距离之和最小为 2 + 2 = 4 > distance = 3，因此在 node 处无法组合任何“好叶子结点对”。同理，在整棵树的每个结点处进行组合，累加得到最终答案。
实现上，dfs(node) 返回一个长为 d + 1（d = distance）的数组 count，记 node 的父结点为 par，count[i] 表示以 par 为根结点的子树中到 par 距离为 i 的叶结点数量。
每次调用 dfs()：
- 对左右子树调用
dfs()获取其count，记为L、R。 - 枚举
L和R中距离之和<= d的叶结点对，累加到答案。 - 将
L和R中叶结点的深度+1，推出自己的count，传递给父结点。
复杂度
- 时间复杂度：
- 空间复杂度：，其中 为树高
代码
Java
class Solution {
private int d, ans = 0;
public int countPairs(TreeNode root, int distance) {
d = distance;
dfs(root);
return ans;
}
private int[] dfs(TreeNode node) {
// 1.特判
// 开到 d+1, 因为关心的最大距离为 d
int[] count = new int[d + 1];
if (node == null) return count;
if (node.left == null && node.right == null) {
// 叶结点, 到 par 的距离为 1
count[1] = 1;
return count;
}
// 2.后序遍历, 获得左右子树的递归结果
int[] L = dfs(node.left), R = dfs(node.right);
// 3.组合并累加
// 组合左右子树中到 node 的距离之和 <=d 的叶结点对, 累加到答案
for (int d1 = 1; d1 <= d; d1++) {
for (int d2 = 1; d1 + d2 <= d; d2++) {
ans += L[d1] * R[d2];
}
}
// 4.推导自己的 count, 向上传递
// 根据左右子树的 count 计算自己的 count, 各叶结点深度 +1
for (int i = 2; i <= d; i++) {
count[i] = L[i - 1] + R[i - 1];
}
return count;
}
}相关题目
LCP 34. 二叉树染色
最后
更多系列「外源推文」&「生活分享」关注公众号：