2024-07-18 1530. Number of Good Leaf Nodes Pairs ※ 引述《oin1104 (是oin的說)》之銘言： : ※ 引述 《oin1104 (是oin的說)》 之銘言： : : 　 : : 　 : : 　 : : 題目 : : : 給你叫做root的樹 : : 還有distance : : 問你樹上所有的兩個葉子之間 : : 在樹上的距離小於等於distance : : 的組合有多少 : 剛剛看到一個很屌的 : 好像是正解 : 就是先假設 : 有兩個葉子 : 一個在左邊 : 深度是1 : 一個在右邊 : 深度是2 : 這樣只要知道他們的深度 : 就可以知道他們的距離了 : 這算什麼演算法阿 : 不太像lca : 然後利用這個去對每個root的葉子 : 做一次看相加有沒有小於的相乘 : 在dfs的時候要用vector 的函式 然後姆咪 : 讓左邊跟右邊的vector 互相看 : 而他們自己都已經是處理完的了 : 然後 : 姆咪 : 可以過濾掉太大的回傳的值 : 時間複雜度是n*D^2 : 不過D很小 所以可以看成n 都被你們講完了我只好照著刻了 對啊 /** * 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), right(right) {} * }; */ class Solution { public: int countPairs(TreeNode* root, int distance) { vector<int> leaf_count(distance); return dfs(root, distance, leaf_count); } private: int dfs(TreeNode* node, int distance, vector<int>&leaf_count) { /* Return: (int): number of valid pairs (vector<int>): number of leaf with depth smaller than distance */ if (!node) { return 0; } if (!node->left && !node->right) { leaf_count[0] = 1; return 0; } vector<int> l_leaf(distance); int l_count = dfs(node->left, distance, l_leaf); vector<int> r_leaf(distance); int r_count = dfs(node->right, distance, r_leaf); int total_count = l_count + r_count; for (int i = 1; i < distance; i++) { leaf_count[i] += l_leaf[i - 1] + r_leaf[i - 1]; for (int j = 1; j < distance; j++) { if (i + j <= distance) { total_count += l_leaf[i - 1] * r_leaf[j - 1]; } } } return total_count; } }; -- ※ 發信站: 批踢踢實業坊(ptt-website.tw), 來自: 73.173.211.221 (美國) ※ 文章網址: https://ptt-website.tw/Marginalman/M.1721279456.A.403