<p>You are given the <code>root</code> of a binary tree and an integer <code>distance</code>. A pair of two different <strong>leaf</strong> nodes of a binary tree is said to be good if the length of <strong>the shortest path</strong> between them is less than or equal to <code>distance</code>.</p>

<p>Return <em>the number of good leaf node pairs</em> in the tree.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/07/09/e1.jpg" style="width: 250px; height: 250px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,null,4], distance = 3
<strong>Output:</strong> 1
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/07/09/e2.jpg" style="width: 250px; height: 182px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,4,5,6,7], distance = 3
<strong>Output:</strong> 2
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the <code>tree</code> is in the range <code>[1, 2<sup>10</sup>].</code></li>
	<li><code>1 &lt;= Node.val &lt;= 100</code></li>
	<li><code>1 &lt;= distance &lt;= 10</code></li>
</ul>

class Solution {
    int bfs(TreeNode *root, int distance, unordered_map<TreeNode*, TreeNode*> &parentMapping) {
        queue<TreeNode*> q;
        q.push(root);
        
        int cnt = 0;
        unordered_set<TreeNode*> visited;
        visited.insert(root);

        while (!q.empty() && distance > 0) {
            int qSize = q.size();

            while (qSize--) {
                TreeNode *node = q.front();
                q.pop();

                if (node->left && visited.find(node->left) == visited.end()) {
                    visited.insert(node->left);
                    
                    if (!node->left->left && !node->left->right) {
                        cnt++;
                    }
                    else {
                        q.push(node->left);
                    }
                }

                if (node->right && visited.find(node->right) == visited.end()) {
                    visited.insert(node->right);
                    
                    if (!node->right->left && !node->right->right) {
                        cnt++;
                    }
                    else {
                        q.push(node->right);
                    }
                }

                if (parentMapping.find(node) != parentMapping.end() && visited.find(parentMapping[node]) == visited.end()) {
                    q.push(parentMapping[node]);
                    visited.insert(parentMapping[node]);
                }
            }

            distance--;
        }

        return cnt;
    }

    void dfs2(TreeNode *root, int &ans, int &distance, unordered_map<TreeNode*, TreeNode*> &parentMapping) {
        if (!root) {
            return;
        }
        
        if (!root->left && !root->right) {
            int cnt = bfs(root, distance, parentMapping);
            cout<<root->val<<" : "<<cnt<<"\n";
            ans += cnt;
        }

        dfs2(root->left, ans, distance, parentMapping);
        dfs2(root->right, ans, distance, parentMapping);
    }

    void dfs1(TreeNode *root, unordered_map<TreeNode*, TreeNode*> &parentMapping) {
        if (!root) {
            return;
        }

        if (root->left) {
            parentMapping[root->left] = root;
            dfs1(root->left, parentMapping);
        }

        if (root->right) {
            parentMapping[root->right] = root;
            dfs1(root->right, parentMapping);
        }
    }

public:
    int countPairs(TreeNode* root, int distance) {
        int ans = 0;
        unordered_map<TreeNode*, TreeNode*> parentMapping;

        dfs1(root, parentMapping);

        dfs2(root, ans, distance, parentMapping);

        return ans / 2;
    }
};
91118