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;
}
};