2024-07-18
1530. Number of Good Leaf Nodes Pairs
※ 引述《oin1104 (是oin的说)》之铭言：
: ※ 引述 《oin1104 (是oin的说)》 之铭言：
: : 　
: : 　
: : 　
: : 题目 :
: : 给你叫做root的树
: : 还有distance
: : 问你树上所有的两个叶子之间
: : 在树上的距离小于等于distance
: : 的组合有多少
: 刚刚看到一个很屌的
: 好像是正解
: 就是先假设
: 有两个叶子
: 一个在左边
: 深度是1
: 一个在右边
: 深度是2
: 这样只要知道他们的深度
: 就可以知道他们的距离了
: 这算什么算法阿
: 不太像lca
: 然后利用这个去对每个root的叶子
: 做一次看相加有没有小于的相乘
: 在dfs的时候要用vector 的函式 然后姆咪
: 让左边跟右边的vector 互相看
: 而他们自己都已经是处理完的了
: 然后
: 姆咪
: 可以过滤掉太大的回传的值
: 时间复杂度是n*D^2
: 不过D很小 所以可以看成n
都被你们讲完了我只好照着刻了
对啊
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
right(right) {}
* };
*/
class Solution {
public:
int countPairs(TreeNode* root, int distance) {
vector<int> leaf_count(distance);
return dfs(root, distance, leaf_count);
}
private:
int dfs(TreeNode* node, int distance, vector<int>&leaf_count) {
/*
Return:
(int): number of valid pairs
(vector<int>): number of leaf with depth smaller than distance
*/
if (!node) {
return 0;
}
if (!node->left && !node->right) {
leaf_count[0] = 1;
return 0;
}
vector<int> l_leaf(distance);
int l_count = dfs(node->left, distance, l_leaf);
vector<int> r_leaf(distance);
int r_count = dfs(node->right, distance, r_leaf);
int total_count = l_count + r_count;
for (int i = 1; i < distance; i++) {
leaf_count[i] += l_leaf[i - 1] + r_leaf[i - 1];
for (int j = 1; j < distance; j++) {
if (i + j <= distance) {
total_count += l_leaf[i - 1] * r_leaf[j - 1];
}
}
}
return total_count;
}
};