※ 引述 《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;
}
};
```