題目 : 給你叫做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-website.tw), 來自: 1.162.33.183 (臺灣) ※ 文章網址: https://ptt-website.tw/Marginalman/M.1721262351.A.1A2

推 sustainer123: 大師 07/18 08:31

推 mrsonic: 一大早的你有什麼用 07/18 08:35

推 SecondRun: 恨JIWP 07/18 08:36

推 smart0eddie: 大師 07/18 08:49