※ 引述 《oin1104 (是oin的说)》 之铭言：
:
:
:
: 题目 :
: 给你叫做root的树
: 还有distance
: 问你树上所有的两个叶子之间
: 在树上的距离小于等于distance
: 的组合有多少
刚刚看到一个很屌的
好像是正解
就是先假设
有两个叶子
一个在左边
深度是1
一个在右边
深度是2
这样只要知道他们的深度
就可以知道他们的距离了
这算什么算法阿
不太像lca
然后利用这个去对每个root的叶子
做一次看相加有没有小于的相乘
在dfs的时候要用vector 的函式 然后姆咪
让左边跟右边的vector 互相看
而他们自己都已经是处理完的了
然后
姆咪
可以过滤掉太大的回传的值
时间复杂度是n*D^2
不过D很小 所以可以看成n
class Solution {
public:
int res ;
int d ;
vector<int> find(TreeNode* root )
{
if(root==NULL)return{};
if(root->left==NULL && root->right==NULL)return{1};
vector<int> l = find(root->left);
vector<int> r = find(root->right);
vector<int> n ;
for(int i = 0 ; i < l.size() ; i ++)
{
for(int j = 0 ; j < r.size() ; j ++)
{
if(l[i]+r[j] <= d)res ++;
}
}
for(int i = 0 ; i < l.size() ; i ++)
{
if(l[i]+1 <= d)n.push_back(l[i]+1);
}
for(int j = 0 ; j < r.size() ; j ++)
{
if(r[j]+1 <= d)n.push_back(r[j]+1);
}
return n;
}
int countPairs(TreeNode* root, int distance)
{
res = 0;
d = distance;
find(root);
return res;
}
};
```