You are 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.

&nbsp;
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].


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [1, 210].
	1 &lt;= Node.val &lt;= 100
	1 &lt;= distance &lt;= 10


class Solution:
    def countPairs(self, root: TreeNode, distance: int) -> int:
        adjList=defaultdict(list)
        leaves=[]
        ct=0
        
        [#undirected graph two way using parent and node in postorder style]
        def dfs(node, parent):
            if node:
                if not node.left and not node.right:
                    leaves.append(node)
                adjList[node].append(parent)
                adjList[parent].append(node)
                dfs(node.left,node)
                dfs(node.right,node)
        
        [#construct graph and get all the leaves]
        dfs(root, None)
        
        #bfs from each leaf till we find another leaf
        for leaf in leaves:
            q=deque([(leaf,0)] )
            seen=set()
            while q:
                curr,dist = q.popleft()
                seen.add(curr)
                if dist>distance:
                    break                
                for nbr in adjList[curr]:
                    if nbr and nbr not in seen:
                        if nbr in leaves and dist+1<=distance:
                            ct+=1
                        q.append((nbr,dist+1))
        
        return ct//2
class Solution {
    static int res;
    public int countPairs(TreeNode root, int distance) {
        res=0;
        rec(root,distance);
        return res;
    }
    static List<Integer> rec(TreeNode root,int dist){
        if(root==null){
            return new LinkedList<Integer>();
        }
        List<Integer> left=rec(root.left,dist);
        List<Integer> right=rec(root.right,dist);
        if(left.size()==0&&right.size()==0){
            List<Integer> temp=new LinkedList<>();
            temp.add(1);
            return temp;
        }
        for(int i:left){
            for(int j:right){
                if(i+j<=dist){
                    res++;
                }
            }
        }
        List<Integer> temp=new LinkedList<>();
        for(int i:left){
            temp.add(i+1);
        }
        for(int i:right){
            temp.add(i+1);
        }
        return temp;
    }
}
class Solution {
    vector<TreeNode*> leaves;
    unordered_map<TreeNode* , TreeNode*> pof;
    void makeGraph(unordered_map<TreeNode* , TreeNode*> &pof, TreeNode* root){
        if(!root) return;
        if(!root->left && !root->right){
            leaves.push_back(root);
            return;
        }
        if(root->left) pof[root->left]=root;
        if(root->right) pof[root->right]=root;
        makeGraph(pof, root->left);
        makeGraph(pof, root->right);
    }
public:
    int countPairs(TreeNode* root, int distance) {
        leaves={};
        makeGraph(pof, root);
        int ans=0;
        queue<pair<TreeNode*, int>> q;
        for(auto &l: leaves){
            q.push({l, 0}); 
            unordered_set<TreeNode*> isVis;
            while(q.size()){
                auto [cur, dist]=q.front();
                q.pop();
                if(isVis.count(cur) || dist>distance) continue;
                isVis.insert(cur);
                if(!cur->left && !cur->right && cur!=l && dist<=distance){
                    ans++;
                    continue;
                }
                if(cur->left && !isVis.count(cur->left)) q.push({cur->left, dist+1});
                if(cur->right && !isVis.count(cur->right)) q.push({cur->right, dist+1});
                if(pof.count(cur) && !isVis.count(pof[cur])) q.push({pof[cur], dist+1});
            }
        }
        return ans>>1;
    }
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} distance
 * @return {number}
 */
var countPairs = function(root, distance) {
    var graph = new Map()
    var leaves = new Map()
    function dfs(root, parent) {
        if (!root) return 
        if (!root.left && !root.right) {
            leaves.set(root, true)
        }

        graph.set(root, [])
        if (root.left) {
            graph.get(root).push(root.left)
        }
        if (root.right) {
            graph.get(root).push(root.right)
        }
        if (parent) {
            graph.get(root).push(parent)
        }
        dfs(root.left, root)
        dfs(root.right, root)
    }  

    dfs(root, null)

    var visited = new Map()
    var count = 0

    function bfs(start, dis) {
        visited.set(start, true)
        var queue = [graph.get(start).filter(node => !visited.has(node))]

        var innerVisited = new Map()

        while (queue.length) {
            var curLevelNodes = queue.shift()

            if (!curLevelNodes.length) break
            if (dis === 0) break

            var nextLevelNodes = []
            for (var i = 0; i < curLevelNodes.length; i++) {
                var curLevelNode = curLevelNodes[i]

                innerVisited.set(curLevelNode, true)

                if (leaves.has(curLevelNode)) {
                    count++
                }

                nextLevelNodes.push(
                    ...graph
                        .get(curLevelNode)
                        .filter(node => 
                            !visited.has(node) && 
                            !innerVisited.has(node)
                        )
                )
               
            }
            queue.push(nextLevelNodes)
            dis--
        }
    }

    leaves.forEach((value, leaf) => {
        bfs(leaf, distance)
    })

    return count
};
Number of Good Leaf Nodes Pairs