题目 :
给你叫做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;
}
};
```