# leetcode 1530. Number of Good Leaf Nodes Pairs LCA 最近公共祖先

#### 题目

https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/
Given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

Example 1:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.
Example 2:

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.
Example 3:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].
Example 4:

Input: root = , distance = 1
Output: 0
Example 5:

Input: root = [1,1,1], distance = 2
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 2^10].
Each node’s value is between [1, 100].
1 <= distance <= 10

#### 源码

``````/**
* 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) {}
* };
*/
struct RES{
int cnt = 0;
vector<pair<int,int>> dis;
};
class Solution {
public:
int dd;
int countPairs(TreeNode* root, int distance) {
dd = distance;
RES res =  dfs(root);
return res.cnt;
}
RES dfs(TreeNode* root){
RES res;
if(root == NULL)return res;
if(root->left==NULL&&root->right==NULL)
res.dis.push_back(make_pair(0,1));
RES l = dfs(root->left);
RES r = dfs(root->right);
res.cnt = l.cnt+r.cnt;
for(int i = 0;i < l.dis.size();++i){
for(int j = 0;j < r.dis.size();++j){
pair<int,int> ll = l.dis[i];
pair<int,int> rr = r.dis[j];
// cout << ll.first<<" "<<rr.first<<" d: "<<ll.second<<" "<<rr.second<<endl;
if(ll.first+rr.first+2<=dd){
res.cnt+=ll.second*rr.second;
}
}
}
//  cout << l.cnt<<endl;
//cout << r.cnt<<endl<<endl;
map<int,int> m;
for(auto p:l.dis){
m[p.first]+=p.second;
}
for(auto p:r.dis){
m[p.first]+=p.second;
}
for(auto p:m){
res.dis.push_back(make_pair(p.first+1,p.second));
}
return res;
}
};
``````

discuss 里看见一份代码同样的逻辑后续遍历，人家代码写的就贼优雅

``````/*
https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/submissions/

Idea is to find out the distance of leaf nodes in left and right subtrees
for each of the parent nodes. For a node 'i', if we know the distance of leaf nodes
in its left and right from it, then we can just check if the sum of distance of the leaf nodes
in left and right <= dist limit, that makes it a good pair.

*/

/**
* 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:
// TC: O(n * d * d), d: max distance limit, n: num of nodes
vector<int> postOrder(TreeNode *root, int &distance,
int &good_leaves) {
// dist(i): no. of leaf nodes with dist 'i' from current node
vector<int> dist(distance + 1, 0);
if(!root)
return dist;

// when current is a leaf node, its distance with its parent will be 1
if(!root->left && !root->right) {
dist = 1;
return dist;
}

// find the distance of leaf and right subtree leaf nodes
auto left_dist = postOrder(root->left, distance, good_leaves);
auto right_dist = postOrder(root->right, distance, good_leaves);

// now check the distances between leaf nodes of leaf and right
// subtrees which are under limit
for(int i = 0; i < left_dist.size(); i++)
for(int j = 0; j < right_dist.size(); j++)
if(i + j <= distance) {
good_leaves += (left_dist[i] * right_dist[j]);
}
// Update the distance for parent and include the current node
for(int i = 1; i <= distance; i++) {
// (i-1) distance becomes distance 'i'
dist[i] = left_dist[i-1] + right_dist[i-1];
}

return dist;
}

int countPairs(TreeNode* root, int distance) {
int good_leaves = 0, curr_dist = -1;
postOrder(root, distance, good_leaves);
return good_leaves;
}
};
``````