C++刷LeetCode（1530. 好叶子节点对的数量）【深度优先搜索】
题目描述：给你二叉树的根节点 root 和一个整数 distance 。
如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对 。
返回树中 好叶子节点对的数量 。
示例 1：
输入：root = , distance = 3
输出：1
解释：树的叶节点是 3 和 4 ，它们之间的最短路径的长度是 3 。这是唯一的好叶子节点对。
示例 2：
输入：root = , distance = 3
输出：2
解释：好叶子节点对为 和 ，最短路径长度都是 2 。但是叶子节点对 不满足要求，因为它们之间的最短路径长度为 4 。
示例 3：
输入：root = , distance = 3
输出：1
解释：唯一的好叶子节点对是 。
示例 4：
输入：root = , distance = 1
输出：0
示例 5：
输入：root = , distance = 2
输出：1
提示：
tree 的节点数在 范围内。
每个节点的值都在 之间。
1 <= distance <= 10
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-good-leaf-nodes-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
* 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:
vector<int> dfs(TreeNode* root, int distance, int& res){
if(root == NULL)return {};
if(root -> left == NULL && root -> right == NULL)return {0};
vector<int> re;
vector<int> temp1 = dfs(root -> left, distance, res);
for(auto& cha : temp1){
if(++cha > distance)continue;//左边要加上右边，所以至少也要++cha这么多距离
re.push_back(cha);
}
vector<int> temp2 = dfs(root -> right, distance, res);
for(auto & cha : temp2){
if(++cha > distance)continue;
re.push_back(cha);
}
for(auto & l : temp1){
for(auto & r : temp2){
res += (l + r <= distance);
}
}
return re;
}
int countPairs(TreeNode* root, int distance) {
int res = 0;
dfs(root, distance, res);
return res;
}
};
参考链接：https://leetcode-cn.com/problems/number-of-good-leaf-nodes-pairs/solution/good-leaf-nodes-pairs-by-ikaruga/
页:
[1]