Re: [閒聊] 每日leetcode已回收
題目 :
給你叫做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;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.33.183 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721262351.A.1A2.html
推
07/18 08:31,
1年前
, 1F
07/18 08:31, 1F
推
07/18 08:35,
1年前
, 2F
07/18 08:35, 2F
推
07/18 08:36,
1年前
, 3F
07/18 08:36, 3F
推
07/18 08:49,
1年前
, 4F
07/18 08:49, 4F
→
07/18 21:24,
1年前
, 5F
07/18 21:24, 5F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 515 之 1554 篇)：