題目 :
給你叫做root的樹
還有distance
問你樹上所有的兩個葉子之間
在樹上的距離小於等於distance
的組合有多少
思路 :
用用看昨天的類似前綴合的東西好了
反正數量不多
就把所有樹葉的路徑記下來
記成LLRRRRLR這種感覺
這樣只要觀察路徑在哪裡開始不一樣
不一樣之後各走了多少步
就可以知道他們的距離
這個做法挺姆咪的
等等看解答
```cpp
/**
* 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), ri
ght(right) {}
* };
*/
class Solution {
public:
vector<string> paper;
string piyan;
void find(TreeNode* root)
{
if(root==NULL)return;
if(root->left==NULL && root->right == NULL)
{
paper.push_back(piyan);
}
piyan.push_back('L');
find(root->left);
piyan.pop_back();
piyan.push_back('R');
find(root->right);
piyan.pop_back();
return ;
}
int jiwp(string a , string b)
{
int ap = 0;
int bp = 0;
int al = a.size();
int bl = b.size();
while(ap<al && bp<al && a[ap]==b[bp])
{
ap++;
bp++;
}
return al-ap + bl-bp;
}
int countPairs(TreeNode* root, int distance)
{
int res = 0;
paper.clear();
find(root);
int len = paper.size();
for(int i = 0 ; i < len ; i++)
{
for(int j = i+1 ; j < len ; j ++ )
{
if(jiwp(paper[i],paper[j]) <= distance)res++;
}
}
return res;
}
};
```